有一个大小为 $$$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
注意
示例和一些最佳解决方案如下图所示。