P5987 [PA 2019] Terytoria

On a 2D Cartesian coordinate plane, there is a map of length $X$ and width $Y$. Note that the left and right boundaries of this map are connected, and the bottom and top boundaries are also connected. On this map, there are $X \times Y$ grid cells and $n$ axis-aligned rectangles. You only know the coordinates of two opposite vertices of each rectangle. In the best case, what is the maximum possible number of grid cells that are covered by all $n$ rectangles?

The first line contains three positive integers $n, X, Y$. The next $n$ lines each contain four integers $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)$, meaning that for the $i$-th rectangle, the coordinates of its two opposite vertices are $(x_1, y_1)$ and $(x_2, y_2)$.

Output one line with one integer: the maximum possible number of grid cells covered by all $n$ rectangles.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$, $2 \le X, Y \le 10^9$. ### Sample Explanation The figure below lists some cases, where the third case is optimal.  Translated by ChatGPT 5