Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить 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 |