Mike的地毯问题

题目描述

Mike的客厅铺满了 m × m 块正方形瓷砖，这些瓷砖形成了一个网格，行从上到下编号为 1 到 m，列从左到右编号为 1 到 m。

地板上铺着 n 块矩形地毯，每块地毯的边都与网格的边平行。每块地毯覆盖若干连续行和若干连续列的交叉区域，形成一个矩形。准确地说，第 i 块地毯由四个整数 xl, xr, yl, yr 描述，其中 1 ≤ xl ≤ xr ≤ m 且 1 ≤ yl ≤ yr ≤ m，表示该地毯覆盖从第 xl 行到第 xr 行、从第 yl 列到第 yr 列的所有瓷砖。

现在，Mike要求你恰好移除一块地毯，使得剩下的不被地毯覆盖的瓷砖数量尽可能多。

换句话说，你需要找出移除哪一块地毯后，剩余不被地毯覆盖的瓷砖数量最大。

输入格式

对于每个测试用例：

• 第一行包含两个整数 n 和 m，分别表示地毯的数量和网格的尺寸，其中 3 ≤ n ≤ 300,000，1 ≤ m ≤ 1500。
• 接下来 n 行，每行包含四个整数 xl, yl, xr, yr，描述一块地毯的位置。 `

输出格式

对于每个测试用例，输出一行一个整数，表示移除一块地毯后，剩余没有地毯覆盖的最大瓷砖数量。

样例输入

4 5
1 1 1 5
2 2 2 3
1 2 3 5
3 5 4 5

样例输出

16