CF1198E.Rectangle Painting 2

There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $\min(h, w)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of $m$ rectangles.

有一个大小为 $n \times n$ 的正方形网格。其中部分格子被染成黑色，其余格子均为白色。在一次操作中，你可以选择某个矩形区域，并将该矩形内的所有格子染成白色。将一个大小为 $h \times w$ 的矩形染白的代价为 $\min(h, w)$。你的目标是以最小总代价将所有格子染成白色。

该正方形网格规模很大，因此我们以压缩形式给出它：所有黑格子的集合是 $m$ 个矩形的并集。

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^{9}$, $0 \le m \le 50$) — the size of the square grid and the number of black rectangles.

Each of the next $m$ lines contains 4 integers $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$) — the coordinates of the bottom-left and the top-right corner cells of the $i$-th black rectangle.

The rectangles may intersect.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^{9}$，$0 \le m \le 50$）—— 分别表示正方形网格的尺寸以及黑色矩形的数量。

接下来的 $m$ 行中，每行包含四个整数 $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$ 个黑色矩形的左下角单元格与右上角单元格的坐标。

这些矩形可以相互相交。

Print a single integer — the minimum total cost of painting the whole square in white.

输出一个整数——将整个正方形涂成白色的最小总代价。

The examples and some of optimal solutions are shown on the pictures below.

示例及部分最优解如下图所示。