0019. Рабочий стол

Имя входного файла:	desktop.in
Имя выходного файла:	desktop.out
Ограничение по времени:	1 s
Ограничение по памяти:	256 megabytes

Рабочий стол новой операционной системы Winux представляет собой прямоугольник M*N пикселов. Каждое окно в этой системе представляет собой прямоугольник, занимающий целое количество пикселов, со сторонами, параллельными границам рабочего стола.

Вася только что установил себе на компьютер эту систему и открыл K окон. И тут его любознательную натуру заинтересовал вопрос, какую часть рабочего стола он может увидеть. Иными словами, сколько пикселов рабочего стола не покрыто ни одним окном.

Сам он найти ответ не смог, зато кропотливо записал координаты левых верхних углов и размеры всех открытых окон. Теперь ваша задача - по этим данным найти ответ на поставленный вопрос.

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

Первая строка входного файла содержит два целых положительных числа M, N - размеры рабочего стола в пикселах по вертикали и горизонтали соответственно (M*N ≤ 10000). Во второй строке записано одно целое неотрицательное число K - количество открытых окон (K ≤ 100000).

Следующие K строк содержат описание окон. В каждой строке находятся по четыре целых числа (x_j, y_j, h_j, w_j). Первые два числа описывают положение левого верхнего угла окна, а вторые два - его размеры по вертикали и горизонтали.

Координаты левого верхнего угла рабочего стола - (1,1), а правого нижнего - (M,N). Гарантируется, что ни одно окно не выходит за границы рабочего стола, то есть (1 ≤ x_j, x_j+hj-1 ≤ M, 1 ≤ y_j, y_j+wj-1 ≤ N). Окна могут накладываться и даже пересекаться.

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

В выходной файл выведите единственное число - количество пикселов рабочего стола, которые не закрыты ни одним окном.

Пример:

desktop.in	desktop.out
5 8 2 1 1 3 2 5 1 1 7	27
4 3 2 2 2 2 2 3 1 1 2	7

Источник: Командное школьное первенство Республики Карелия по программированию, октябрь 2008.

Обсудить       Отправить решение



Версия для печати