1690 - 综合练习-machine do farmwork

Farmer John 为了让自己从无穷无尽的犁田工作中解放出来,于是买了个新机器人帮助他犁田。这个机器人可以完成犁田的任务,可惜有一个小小的缺点:这个犁田机器人一次只能犁一个边的长度是整数的长方形的田地。

因为 FJ 的田地有树和其它障碍物,所以 FJ 设定机器人去犁很多不同的长方形。这些长方形允许重叠。他给机器人下了 $r$ 个指令,每个指令包含一个要犁长方形的地,这片田地由长方形的左下角和右上角坐标决定。

一般来说,田地被分割为很多小方格。这些方格的边和 $x$ 轴或 $y$ 轴平行。田地的长度为 $n$ 个方格,宽度为 $m$ 个方格. FJ 执行了 $r$ 个指令,每个指令包含 $4$ 个整数:$x_1,y_1,x_2,y_2$, 分别是要犁的长方形的左下角坐标和右上角坐标。机器人会犁所有的在这个长方形范围内的地,他很好奇最后到底有多少个方格的地被犁过了。

输入

第一行三个整数 $n,m,r$,分表表示田的长和宽,以及指令的数量。

接下来 $r$ 行,每行四个整数 $x_1,y_1,x_2,y_2$,表示要犁的长方形的左下角坐标和右上角坐标,满足 $1\le x_1 \le x_2 \le n$,$1\le y_1 \le y_2 \le m$。

数据范围: $1\le n,m\le 240,1 \le 200 \le r$。

输出

输出一个整数,表示指令执行完后有多少个方格的地被犁过了。

样例

输入

6 4 2 
1 1 2 4 
1 3 5 4 

输出

14
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题