DRŽAVNO NATJECANJE 2014. - Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 2. zadatak

Direktorica Eva želi otvoriti dva nova odjela u poduzeću koje vodi kako bi u sljedećoj godini ostvarila sve ambiciozne projekte koje je zamislila.

Sada pokušava odrediti koliko je stručnjaka potrebno zaposliti u svakom od odjela kako bi se svi projekti uspješno izvršili.

Eva je zamislila N projekata, a projekt s rednim brojem K bit će izvršen ukoliko prvom odjelu bude dodijeljeno barem XK zaposlenika ili ako drugom odjelu bude dodijeljeno barem YK zaposlenika (ili oboje).

Ukupan potreban broj novih zaposlenika definira se kao zbroj zaposlenika dodijeljenih svakom od dva odjela.

Pomognite Evi odrediti minimalan ukupan broj novih zaposlenika tako da svi zacrtani planovi budu ispunjeni.

Ulazni podaci

U prvom redu nalazi se prirodni broj N (1 ≤ N ≤ 100 000), broj zamišljenih projekata.

U svakom od sljedećih N redova nalaze se prirodni brojevi XK, YK (1 ≤ XK, YK ≤ 1 000 000 000) iz teksta zadatka.

Izlazni podaci

U prvi i jedini red ispišite minimalan broj novih zaposlenika koji omogućuje da se svi projekti izvrše.

Primjer zadatka

Ulaz

1
7 4

Izlaz

4

Ulaz

2
5 20
20 5

Izlaz

10

Ulaz

3
3 3
7 20
100 6

Izlaz

13

Objašnjenje

Pojašnjenje trećeg test primjera: Ukoliko prvom odjelu dodijelimo 7 zaposlenika, a drugom odjelu 6

zaposlenika, tada će svi projekti biti izvršeni, a ukupan broj novih zaposlenika je 13.