e-olymp

ACM

prb312

Ассоциация шахматных монстров (АСМ - Association of Chess Monsters) планирует свой ежегодный матч против команды остального мира. Матч будет проходить на 30 досках, где в каждой команде 15 игроков будут играть белыми и 15 игроков - черными. В команде АСМ много игроков, и они хотят выставить наилучшую команды, которую смогут. Рейтинг каждого игрока для игры белым цветом измеряется по шкале от 1 до 100 и точно так же для игры черными. Во время матча игрок может играть только одним цветом, т.е. только белыми или черными. Значение рейтинга команды равна сумме рейтингов игроков, которые будут играть белыми, и рейтингов игроков, которые будут играть черными. Помогите команде ACM собрать команду с наиболее высоким общим рейтингом.

Входные данные

Входные данные состоят из последовательности строк с рейтингами игроков. Каждая строка описывает рейтинг одного игрока двумя целыми числами, разделенных пробелами. Первое число это рейтинг игрока при игре белыми, а второе - черными. Гарантируется, что во входных данных не менее 30 и не более 1000 строк.

Выходные данные

Выведите одну строку, содержащую целое число - величину рейтинга лучшей шахматной команды ACM, которую удастся собрать.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
87 84
66 78
86 94
93 87
72 100
78 63
60 91
77 64
77 91
87 73
69 62
80 68
81 83
74 63
86 68
53 80
59 73
68 70
57 94
93 62
74 80
70 72
88 85
75 99
71 66
77 64
81 92
74 57
71 63
82 97
76 56
Выходные данные
2506