placi

Момчето Дънут има две мишки: Джери и Тери. Дънут решава да направи експеримент: след като мишките заспали, той построил разделяща ги стена от ... сирене. За този експеримент момчето било купило N парчета  различни видове сирене. За i-тото парче  (i = 1,…, N) е известно времето, за което то може да бъде изядено от Джери  (за ai секунди) или от Тери (за bi секунди).
На сутринта двете мишки се събудили едновременно и веднага започнали да "разрушават" стената от противоположните й краища. Парчетата сирене те разрушавали последователно, без прекъсване и с постоянна скорост за всяко парче, като всяко парче е било изяждано изцяло, преди да преминат към следващото. Мишките не се скарали, когато трябвало да разрушават едно и също парче, т.е. всяка мишка продължила да яде частта си от последното парче с постоянната скорост, докато може. Стената считаме за разрушена, когато и последното парче е изядено.
Дънут иска да нареди парчетата сирене така, че стената да съществува максимално дълго време. Времето се измерва от момента на събуждането на мишките до момента на разрушаване на стената.

Задача

Напишете програма, която да определи максималното време за съществуване на стената.

Вход

Входният файл placi.in съдържа в първия си ред едно положително цяло число N, равно на броя на парчетата. Всеки от следващите N реда съдържа по 2 положителни цели числа, ai и bi, отделени с интервал, задаващи времето за което i-тото парче може да бъде изядено съответно от Джери и от Тери.

Изход

Изходният файл placi.out трябва да съдържа един ред с едно положително число с десетична точка и с поне 3 цифри след нея,

с което вашата програма определя максималното време за съществуване на стената.

Резултатът се приема за правилен, ако абсолютната стойност на разликата между записаното във файла число и верния отговор е по-малка или равна на 0.001.

 

Ограничения

Пример

placi.in

placi.out

placi.in

placi.out

4
1 2
1 2
0.5 1.5
7 3.5

6.000

1
3 6

2.000

Time limit: 0.1 сек за тест.

prof. Sergiu Corlat
Chişinău Moldavian-Turkish High-School, Republic of Moldova
Contact:scorlat
@gmail.com

Превод на български: Емил Келеведжиев