P17475 [ICPC 2018 Jiaozuo R] Carpets Removal

Mike 的客厅铺满了 $m^2$ 块正方形地砖。这些地砖构成一个 $m \times m$ 的网格，其中行从上到下依次标号为 $1$ 到 $m$，列从左到右依次标号为 $1$ 到 $m$。 :::align{center}  ::: 在这些地砖之上，铺有 $n$ 块矩形地毯，其各边均平行于网格的边。每块地毯覆盖了若干连续行和若干连续列的交集，形成一个矩形区域。确切地说，其中第 $i$ 块地毯由四个整数 $x_l, x_r, y_l, y_r$ 描述，且满足 $1 \leq x_l \leq x_r \leq m$ 和 $1 \leq y_l \leq y_r \leq m$，表示该地毯覆盖了所有既在第 $x_l$ 行到第 $x_r$ 行之间、又在第 $y_l$ 列到第 $y_r$ 列之间的地砖。 现在 Mike 要求你**恰好取走两块**地毯，以使得仍被至少一块剩余地毯覆盖的地砖数量最少。 上图描述了样例中的场景，其中两块由虚线边界标示的矩形区域表示了移除两块地毯的一种最优方案。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多为 $1000$。 对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，分别表示地毯的数量和每行（或每列）的地砖数，满足 $3 \leq n \leq 3 \times 10^5$ 且 $1 \leq m \leq 1500$。 接下来的 $n$ 行，每行包含四个整数 $x_l$, $x_r$, $y_l$, $y_r$，描述一块铺设在地面的地毯及其位置，满足 $1 \leq x_l \leq x_r \leq m$ 且 $1 \leq y_l \leq y_r \leq m$。 我们保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^6$，所有测试数据中 $m^2$ 的总和不超过 $5 \times 10^7$。

对于每组测试数据，输出一行包含一个整数，即在移除两块地毯后，仍被至少一块剩余地毯覆盖的地砖的最少数量。

翻译由 DeepSeek V4 Pro 完成