Description

莉莉和娜娜正在莉莉家后院除草。她们反复选择矩形区域，并移除其中的所有草坪。

后院可以被视为一个二维网格，每个方格表示一个单位面积。她们共进行了 $n$ 次操作。在第 $i$ 次操作中，她们选择了一个矩形的左、下、右、上的边界，分别表示为 $l_i, b_i, r_i, t_i$，并使用割草机清除该矩形内的所有方格。注意，这些矩形可能会相互重叠。

用 $[l_i, r_i] \times [b_i, t_i]$ 表示一个矩形。

以下是一个例子，如图所示。她们选择了 $2$ 个矩形，第一个矩形是 $[1, 5] \times [2, 3]$，第二个矩形是 $[2, 3] \times [1, 4]$。

经过 $n$ 次除草操作后，裸露区域的联合可能不连通，但所有边都是水平或垂直的。因此，联合区域变成了一个或多个直角多边形，其中一些可能包含多边形孔洞。此外，在某些孔洞内部可能会有裸露的方格。更多细节和图示请参见示例输入。

现在，她们想通过在裸露的方格上种植植物来恢复土地。莉莉喜欢多边形，特别是矩形。因此，她们想选择若干个矩形，这些矩形之间不重叠，并且能够完全覆盖所有的裸露方格。然后，她们将在选择的不同矩形中种植不同的植物。

例如，下面是上述情况的一个可行的矩形选择：选择 $[1, 1] \times [2, 3]$、$[2, 3] \times [1, 4]$ 和 $[4, 5] \times [2, 3]$。

玩了一会儿，这两个小女孩已经累了，所以她们想知道覆盖所有裸露方格的最小不重叠矩形数量。

Input Format

第一行包含一个整数 $n$ ($1 \leq n \leq 300$) —— 表示除草时使用的矩形数量。

接下来的 $n$ 行每行包含 $4$ 个整数，第 $i$ 行包含 $l_i, b_i, r_i, t_i$ ($1 \leq l_i, b_i, r_i, t_i \leq 10^9, l_i \leq r_i, b_i \leq t_i$) —— 表示第 $i$ 个矩形的左、下、右、上边界。

保证裸露区域的端点总数（多边形及其孔洞）不超过 $2000$。

Output Format

在一行上输出一个整数，表示覆盖所有裸露方格所需选择的最小矩形数量。

8
1 1 1 1
1 2 1 2
1 3 1 3
2 1 2 1
2 3 2 3
3 1 3 1
3 2 3 2
3 3 3 3

4

2
1 1 100 100
1 501 100 600

2

4
1 1 4 1
1 4 5 4
1 1 1 4
4 1 4 5

5

9
1 1 9 1
1 1 1 9
1 9 9 9
9 1 9 9
3 3 7 3
3 3 3 7
3 7 7 7
7 3 7 7
5 5 5 5

9

Hint

对于第一个例子，最优选择是 $[1, 1] \times [1, 3]$、$[2, 1] \times [2, 1]$、$[2, 3] \times [2, 3]$ 和 $[3, 1] \times [3, 3]$。

对于第二个例子，最优选择是 $[1, 1] \times [100, 100]$ 和 $[1, 501] \times [100, 600]$。

对于第三个例子，最优选择是 $[1, 1] \times [4, 1]$、$[1, 4] \times [5, 4]$、$[1, 2] \times [1, 3]$、$[4, 2] \times [4, 3]$ 和 $[4, 5] \times [4, 5]$。

对于第四个例子，裸露区域如下图所示。

翻译者：Immunoglobules