Автор: | И. Блинов | Ограничение времени: | 5 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства pi (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает ci. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.
Слон Пахом тренер одной из команд, и он нашёл способ схитрить, а именно переместить одного боксёра в другую весовую категорию. Теперь он хочет максимизировать разницу между количеством побед боксёров своей команды и боксёров команды противника.
Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел pi, wi — описание боксёров из команды Пахома. Далее N пар чисел pi, wi — описание команды соперников.
Выходной файл должен содержать одно число — максимальная разница очков которую может получить команда Пахома.
1 ≤ N ≤ 106, 1 ≤ M ≤ 300, 1 ≤ сi ≤ M; 1 ≤ pi ≤ 109.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
N | M | |||
1 | 20 | 1 ≤ N ≤ 20 | 1 ≤ M ≤ 2 | |
2 | 20 | 1 ≤ N ≤ 1000 | 1 ≤ M ≤ 2 | |
3 | 20 | 1 ≤ N ≤ 106 | 1 ≤ M ≤ 2 | |
4 | 20 | 1 ≤ N ≤ 106 | 1 ≤ M ≤ 50 | |
5 | 20 | 1 ≤ N ≤ 106 | 1 ≤ M ≤ 300 |
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|