Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Интересная игра c числами

(Время: 1 сек. Память: 16 Мб Сложность: 48%)

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

A1A2A3...AN
B1B2B3...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.TXTOUTPUT.TXT
11
1 1
1
22
1 1
1 1
0
33
1 2
3 4
5 6
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru