#P1899. Farmer Bill's Problem

Farmer Bill's Problem

描述描述
据传闻,地球时常有不明飞行物(UFO)造访。有时UFO着陆后会留下烧焦区域,观察显示这些区域呈圆形。

最近,农民比尔在他那片规整的矩形麦田里发现了这样的圆形区域。比尔对所有神秘事物都极为喜爱,因此决定将麦田里的这些圆形区域保留下来。不过,尽管他是一名UFO研究者,但比尔首先是个农民,他需要收割小麦。于是他打算保留一些包含圆形的矩形区域,这些矩形既不接触也不重叠,且其边与麦田的边平行,而所有UFO留下的圆形必须完全处于这些矩形内部。为了能收割尽可能多的麦田,保留区域的总面积需尽可能小。

现在比尔想知道他能够收割的麦田面积,快来帮帮他吧!

输入输入
输入的第一行包含两个整数xxyy1x,y10001 \leq x, y \leq 1000),表示比尔麦田的尺寸。假设比尔的麦田在平面上的位置使得其四个角的坐标分别为(0,0)(0, 0)(x,0)(x, 0)(x,y)(x, y)(0,y)(0, y)。输入的第二行是NN0N1000 \leq N \leq 100),表示比尔麦田里UFO留下的圆形数量。接下来的NN行每行描述一个圆形,包含三个正整数xix_iyiy_irir_i,分别表示圆心坐标和半径。这些圆形可能相切、重叠或者相互包含,但全都完全位于麦田边界之内。

输出输出
输出一个整数,即比尔能够收割的麦田部分的面积。

输出

输出一个整数,表示比尔能够收割的麦田部分的面积。

输入数据

10 8
2
3 3 1
1 1 1

输出数据

64