Processing math: 100%

Задача D. Чемпионат по боксу

Автор:И. Блинов   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства pi (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает ci. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

Слон Пахом тренер одной из команд, и он нашёл способ схитрить, а именно переместить одного боксёра в другую весовую категорию. Теперь он хочет максимизировать разность между количеством побед боксёров своей команды и боксёров команды противника.

Формат входного файла

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел pi, сi  — описание боксёров из команды Пахома. Далее N пар чисел pi, сi  — описание команды соперников.

Формат выходного файла

Выходной файл должен содержать одно число  — максимальная разница очков которую может получить команда Пахома.

Ограничения

1N106,1M300,1сiM;1pi109.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Дополнительные ограничения
NM
1201N201M2
2201N10001M2
3201N1061M2
4201N1061M50
5201N1061M300

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
1 1
2 1 
3 1
4 1
5 1
6 1
-9
2
4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2
12
3
3 3
5 1
10 2
15 3
6 1
11 2
16 3
-1

0.069s 0.008s 13