Участник игры в морской бой размещает на игровом поле свои корабли. По правилам этой разновидности игры корабли могут быть только прямоугольниками любых размеров, не могут пересекаться и иметь общих граничных точек. Количество уже размещённых кораблей равно K. Последний корабль он хочет сделать максимально большим.
В первой строке входного файла INPUT.TXT записаны три числа N, M и K – количество клеток по вертикали, количество клеток по горизонтали и число уже выстроенных кораблей соответственно (1 ≤ N, M ≤ 100, 1 ≤ K ≤ 10). Следующие K строк содержат координаты K размещённых кораблей – 4 числа в каждой строке. 1-е и 2-е число – вертикальная и горизонтальная координаты левой верхней угловой клетки корабля, 3-е и 4-е число – вертикальная и горизонтальная координаты правой нижней угловой клетки корабля. Клетки поля нумеруются сверху вниз (от 1 до N) и слева направо (от 1 до M).
В выходной файл OUTPUT.TXT выведите одно число – количество клеток в последнем корабле.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 7 3
1 1 2 2
3 5 3 7
4 2 4 3
| 21 |
