26296번 - Dihotomna Dioba 다국어

Junak našeg doba Patrick je na pomolu najteže odluke u svom životu. Nakon odlične, fenomenalne i neponovljive večeri s društvom našao se u škripcu.

Petak je navečer. Trg je obojan u bezbroj boja. Čuje se buka preko sto čeljadi. Hladni vjetrić koji najavljuje zimu definitivno ne pomaže u aktivaciji moždanih vijuga. U uvjetima u kojima jedva i ban može ostati miran, Patrick nervozno korača naprijed. Broj kamenih ploča do tramvajske pruge svake sekunde sve je manji, a Patrick mora odlučiti.

Naime, Jelena i Ana bi obje voljele da ih Patrick otprati kući, no unatoč mišljenjima mnogih čak i njegove sposobnosti su ograničene.

Kada skoro sva nada bijaše izgubljena, gurajući ruku u džep, Patrick na svom desnom kažiprstu osjeti rub pažljivo sedam puta presavinutog papirića kojeg mu je par sati prije dao mudrac Ivan riječima: “Možda ti neće odmah biti jasno čemu ovo služi, ali kada dođe vrijeme shvatit češ.‚‚

Nanovo inspirirani Patrick odmah je prepoznao da je riječ o zagonetci u kojoj se pravokutnici trebaju složiti jedan na drugi formirajući toranj.

Zadano je n pravokutnika sa zadanim visinama i širinama. Potrebno je složiti toranj tako da se točno jedan pravokutnik nalazi na dnu te se iznad svakog pravokutnika (osim onog na vrhu) nalazi točno jedan pravokutnik čija je širina strogo manja.

Pravokutnike je dopušteno rotirati za 90 stupnjeva (mijenjajući pritom visinu i širinu) te je potrebno iskoristiti sve pravokutnike.

Patrick je shvatio da je ipak najpametnije otići kući i pokušati složiti što je viši mogući toranj.

U prvom retku nalazi se prirodan broj n (1 ≤ n ≤ 250 000) iz teksta zadatka.

U sljedećih n redaka nalaze se po dva prirodna broja koja predstavljaju veličine stranica pojedinog pravokutnika. Veličine stranica su prirodni brojevi manji ili jednaki od 10⁹.

U jedini redak ispišite maksimalnu visinu tornja kojeg je moguće složiti koristeći sve pravokutnike prema pravilima opisanim u zadatku.