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

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

HotLog


 

Ключи

(Время: 5 сек. Память: 32 Мб Сложность: 61%)

Для доступа в лаборатории НИИ Исследований Данных Строк используются ключи в виде прямоугольных карточек N×M, в которых вырезаны дырки. Эти ключи можно вставлять только одним способом (то есть ни поворачивать, ни переворачивать нельзя). При этом дырки имеют прямоугольную форму. К Васе попало два ключа от разных лабораторий. Он решил их наложить друг на друга так, чтобы получившаяся фигура имела максимальное количество дырок (просветов). При этом исходно ключи лежали в том положении, в котором их необходимо вставлять в замок, а Вася не хочет их поворачивать. Помогите Васе определить максимальное число дырок. При наложении считаются только те дырки, внутренности которых не пусты.

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

Первая строка входного файла INPUT.TXT содержит два целых числа - 1 ≤ N, M ≤ 109 - длины сторон ключа. Вторая строка содержит единственное целое число - 1 ≤ K1 ≤ 500 - число дырок в первом ключе. Далее в K1 строках написано по четыре целых числа - X1, Y1, X2, Y2 (0 ≤ X1 < X2 ≤ N, 0 ≤ Y1 < Y2 ≤ M) – координаты углов соответствующих прямоугольных дырок. Дырки в ключе не пересекаются и не касаются.

Далее следует описание второго ключа в таком же формате.

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

В выходной файл OUTPUT.TXT выведите единственное целое число - максимальное количество дырок, которое может получить Вася.

Примеры

INPUT.TXTOUTPUT.TXT
110 10
1
1 1 2 2
1
1 1 2 2
1
210 10
2
1 1 2 2
3 3 4 4
1
1 1 2 2
1
310 10
2
1 1 2 2
3 3 4 4
1
1 1 3 3
2

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483