Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M
своих коров (M <=
109, M
- чётное) на M/2
пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.
Каждая из коров даёт различное количество молока. Если коровы в паре дают по A
и B
литров молока, то для дойки этой пары требуется A+B
единиц времени.
Помогите ФД определить минимально возможное количество времени на весь процесс дойки, в предположении, что коровы разбиты на пары наилучшим образом.
Входные данные
Первая строка ввода содержит N
(1 <= N
<= 100000). Каждая из следующих N
строк содержит два целых числа x
и y
, указывающих, что у ФД есть x
коров с производством молока по y
(1 <= y
<=
109) литров. Сумма всех x-ов есть M
- общее количество коров.
Выходные данные
Выведите минимальное количество времени, которое займёт дойка всех коров, в предположении, что они разбиты на пары оптимальным образом.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3
1 8
2 5
1 2
|
10 |