83454 - Terytoria

通过次数

2

提交次数

8

时间限制 : 4 秒
内存限制 : 256 MB

在二维平面直角坐标系上,有一个长度为 X,宽度为 Y 的地图,注意这个地图的左边界和右边界是连通的,下边界和上边界也是连通的。

在这个地图里,有 X\times Y 个格子以及 n 个边平行坐标轴的矩形。你只知道每个矩形两个对顶点的坐标,请问在最好情况下,被所有 n 个矩形都覆盖住的格子数量有多少?

输入

第一行三个正整数 n,X,Y

接下来 n 行,每行四个整数 x_1,y_1,x_2,y_2(0\le x_1,x_2 < X,0\le y_1,y_2 < Y,x_1\ne x_2,y_1\ne y_2),表示第 i 个矩形两个对顶点的坐标为 (x_1,y_1)(x_2,y_2)

输出

输出一行一个整数,即被所有 n 个矩形都覆盖住的格子数量的最大可能值。

样例

输入

2 10 7
2 1 8 6
5 2 4 4

输出

15

提示

对于 100\% 的数据,1\le n\le 5\times 10^52\le X,Y\le 10^9

来源

PA