← 返回题目列表

Codeforces · 1198/E

E. 矩形绘画 2

中文机器翻译题面 查看原题

有一个大小为 $$$n \times n$$$ 的方形网格。一些细胞呈黑色,所有其他细胞呈白色。在一项操作中,您可以选择某个矩形并将其所有单元格着色为白色。为大小为 $$$h \times w$$$ 的矩形着色的成本为 $$$\min(h, w)$$$。您将以最小的总成本将所有单元格设置为白色。

这个正方形很大,所以我们以压缩的方式给你。黑色单元格集是 $$$m$$$ 矩形的并集。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^{9}$$$, $$$0 \le m \le 50$$$) - 方形网格的大小和黑色矩形的数量。

接下来的 $$$m$$$ 行包含 4 个整数 $$$x_{i1}$$$ $$$y_{i1}$$$ $$$x_{i2}$$$ $$$y_{i2}$$$ ($$$1 \le x_{i1} \le x_{i2} \le n$$$, $$$1 \le y_{i1} \le y_{i2} \le n$$$) — 第 $$$i$$$ 个黑色矩形的左下角和右上角单元格的坐标。

矩形可能相交。

输出

打印一个整数——将整个正方形涂成白色的最小总成本。

示例

输入 #1

10 2
4 1 5 10
1 4 10 5

输出 #1

4

输入 #2

7 6
2 1 2 1
4 2 4 3
2 5 2 5
2 3 5 3
1 2 1 2
3 2 5 3

输出 #2

3

注意

示例和一些最佳解决方案如下图所示。