Жадный алгоритм

Интересная игра c числами
Рассмотрим следующую интересную игру для двух игроков. Для этой игры необходима таблица из 2-х строк и N столбцов, в клетках которой записаны натуральные числа, следующего вида:

A1 A2 A3 ... AN
B1 B2 B3 ... BN

Игроки делают ходы по очереди. Начинает игру 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
1
1 1
OUTPUT.TXT
1
INPUT.TXT
2
1 1
1 1
OUTPUT.TXT
0
INPUT.TXT
3
1 2
3 4
5 6
OUTPUT.TXT
2

0