Poster

Tâche

Dans sa chambre, Stofl la souris a un mur sur lequel il affiche ses posters. Comme il est paresseux, il n'enlève jamais de posters, il colle simplement les nouveaux par dessus les vieux. De cette façon, certains des posters se superposent, mais il y a encore des parties du mur qui ne sont pas cachées. Stofl aimerait maintenant savoir quelle est la surface totale du mur qui n'est pas cachée.

Entrée

Dans la première ligne de l'entrée, il y a trois entiers séparés par des espaces: $W$, $H$ et $N$, la largeur et la hauteur du mur ainsi que le nombre total de posters. Chacune des $N$ lignes suivantes contient quatre entiers, séparés par des espaces, qui décrivent un poster: $x_i$ et $y_i$, les distances horizontale et verticale du coin supérieur gauche du mur au coin supérieur gauche du poster, suivis par $w_i$ et $h_i$, la largeur et la hauteur du poster.

Sortie

La sortie doit contenir un entier, la surface du mur qui n'est couverte par aucun poster.

Limites

Pour chaque poster, $x_i, y_i \geq 0$ et $w_i, h_i > 0$; $x_i+w_i \leq W$ et $y_i+h_i \leq H$.

Si ton programme traite correctement les cas avec $1 \leq W,H,N \leq 200$, tu obtiendras 70% des points. Pour obtenir tout les points, les limites sont $1 \leq W,H \leq 10^9$ et $1 \leq N \leq 500$.

Exemple 1

InputOutput

8 6 3
1 1 3 2
6 1 2 2
3 2 2 3

33

Exemple 2

InputOutput

7 6 3
1 2 3 2
3 1 2 4
0 1 6 3

22

Explication

Ci-dessous, tu peux voir une représentation du mur de Stofl pour les exemples 1 et 2 (les '.' représentent les surfaces non couvertes, les '\#' représentent les surfaces couvertes).

........
.###..##
.####.##
...##...
...##...
........
.......
######.
######.
######.
...##..
.......

Envoi