|
Ключи
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 10 10
1
1 1 2 2
1
1 1 2 2 | 1 |
| 2 | 10 10
2
1 1 2 2
3 3 4 4
1
1 1 2 2 | 1 |
| 3 | 10 10
2
1 1 2 2
3 3 4 4
1
1 1 3 3 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
