Интересная игра c числами
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Рассмотрим следующую интересную игру для двух игроков. Для этой игры необходима таблица из 2-х строк и N столбцов, в клетках которой записаны натуральные числа, следующего вида:
Игроки делают ходы по очереди. Начинает игру 1-й игрок.
За один ход 1-й игрок выполняет следующие два действия:
- выбирает произвольный столбец (к примеру, j-й), который еще ни разу не был выбран одним из игроков на предыдущих ходах;
- прибавляет к своим очкам число Aj.
За один ход 2-й игрок выполняет следующие два действия:
- выбирает произвольный столбец (к примеру, j-й), который еще ни разу не был выбран одним из игроков на предыдущих ходах;
- прибавляет к своим очкам число Bj.
Игра заканчивается, когда какой-либо из игроков не сможет сделать ход (по той причине, что все столбцы уже были выбраны). Изначально, у каждого из игроков есть 0 очков.
После того, как игра закончилась, происходит взаиморасчет между игроками. К примеру, 1-й игрок набрал S1 очков, а 2-й игрок - S2 очков. В случае, когда S1 > S2, 2-й игрок отдает 1-му игроку S1-S2 УДЕ (условных денежных единиц). В противном случае, 1-й игрок отдает 2-му игроку S2-S1 УДЕ. С этих позиций, целью 1-го игрока является максимизация величины S1-S2, а целью 2-го игрока - максимизация S2-S1.
Назовем стоимостью игры величину S1-S2 при оптимальной игре обоих игроков. Напишите программу, которая определяет стоимость игры.
Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число N - количество столбцов в таблице (1 ≤ N ≤ 300000). Следующие N строк описывают числа в столбцах таблицы. i-я из этих строк содержит два натуральных числа Ai и Bi, разделенные одним пробелом (1 ≤ Ai, Bi ≤ 3000).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число - стоимость игры.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
1 1 | 1 |
| 2 | 2
1 1
1 1 | 0 |
| 3 | 3
1 2
3 4
5 6 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
