[AdditionalFile3220.zip](file://AdditionalFile3220.zip?type=additional_file)

#3220. 「PA 2019」Terytoria

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2019 Runda 3 Terytoria

在二维平面直角坐标系上，有一个长度为 $X$，宽度为 $Y$ 的地图，注意这个地图的左边界和右边界是连通的，下边界和上边界也是连通的，换言之它是个球形结构。

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

输入格式

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

接下来 $n$ 行，每行四个整数 $x_1, y_1, x_2, y_2$，表示第 $i$ 个矩形两个对顶点的坐标为$(x_1, y_1)$ 和 $(x_2, y_2)$。

输出格式

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

样例

输入

2 10 7
2 1 8 6
5 2 4 4

输出

15

下图列举了一些情况，其中第 3 种情况是最优的。

数据范围与提示

$1 \le n \le 5\times 10^5, 2 \le X, Y \le 10^9, 0 \le x_1, x_2 < X, 0 \le y_1, y_2 < Y, x_1 \ne x_2, y_1 \ne y_2$