Олимпиадный тренинг

Задача . Paired Up


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

Выходные данные
Выведите минимальное количество времени, которое займёт дойка всех коров, в предположении, что они разбиты на пары оптимальным образом.

 
Примеры
Входные данные Выходные данные
1
3
1 8
2 5
1 2
10

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6427
Python23
Комментарий учителя