Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: 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


 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: