Задача: Paired Up
Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M≤1,000,000,000, MM - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.
Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.
Помогите ФД определить минимально возможное количество времени на весь процесс дойки, в предположении, что коровы разбиты на пары наилучшим образом.
ФОРМАТ ВВОДА :
Первая строка ввода содержит N (1≤N≤100,000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть xx коров с производством молока по y (1≤y≤1,000,000,000) литров. Сумма всех x-ов есть M - общее количество коров.
ФОРМАТ ВЫВОДА:
Выведите минимальное количество времени, которое займёт дойка всех коров, в предположении, что они разбиты на пары оптимальным образом.
|
Ввод |
Вывод |
|
3
1 8
2 5
1 2
|
10 |
Ваш ответ: