CF793G.Oleg and chess

Oleg the bank client solves an interesting chess problem: place on n × n chessboard the maximum number of rooks so that they don't beat each other. Of course, no two rooks can share the same cell.

Remind that a rook standing in the cell (a, b) beats a rook standing in the cell (x, y) if and only if a = x or b = y.

Unfortunately (of fortunately?) for Oleg the answer in this problem was always n, so the task bored Oleg soon. He decided to make it more difficult by removing some cells from the board. If a cell is deleted, Oleg can't put a rook there, but rooks do beat each other "through" deleted cells.

Oleg deletes the cells in groups, namely, he repeatedly choose a rectangle with sides parallel to the board sides and deletes all the cells inside the rectangle. Formally, if he chooses a rectangle, lower left cell of which has coordinates (_x_1, _y_1), and upper right cell of which has coordinates (_x_2, _y_2), then he deletes all such cells with coordinates (x, y) that _x_1 ≤ x ≤ _x_2 and _y_1 ≤ y ≤ _y_2. It is guaranteed that no cell is deleted twice, i.e. the chosen rectangles do not intersect.

This version of the problem Oleg can't solve, and his friend Igor is busy at a conference, so he can't help Oleg.

You are the last hope for Oleg! Help him: given the size of the board and the deleted rectangles find the maximum possible number of rooks that could be placed on the board so that no two rooks beat each other.

银行客户奥列格正在解决一个有趣的国际象棋问题：在 $n \times n$ 的棋盘上放置尽可能多的车（rook），使得它们互不攻击。显然，任意两个车不能占据同一格子。

请回忆：位于格子 $(a,\,b)$ 的车会攻击位于格子 $(x,\,y)$ 的车，当且仅当 $a = x$ 或 $b = y$。

不幸的是（抑或幸运？）——该问题的答案恒为 $n$，因此很快令奥列格感到乏味。他决定通过从棋盘上移除若干格子来增加难度。若某格子被删除，则奥列格无法在该格子上放置车；但车仍可“穿过”被删除的格子相互攻击。

奥列格以“组”的方式删除格子：即反复选取一组边与棋盘边平行的矩形，并删除每个矩形内部的所有格子。形式化地，若他选取一个矩形，其左下角格子坐标为 $(x_1,\,y_1)$，右上角格子坐标为 $(x_2,\,y_2)$，则他将删除所有满足 $x_1 \le x \le x_2$ 且 $y_1 \le y \le y_2$ 的格子 $(x,\,y)$。题目保证任一格子至多被删除一次，即所选矩形两两不相交。

这一版本的问题奥列格已无法解决，而他的朋友伊戈尔正忙于参加学术会议，无法提供帮助。

你便是奥列格最后的希望！请帮助他：给定棋盘大小及所有被删除的矩形，求出可在剩余格子上放置的、互不攻击的车的最大数量。

The first line contains single integer n (1  ≤  n ≤  10000) — the size of the board.

The second line contains single integer q (0  ≤  q  ≤  10000) — the number of deleted rectangles.

The next q lines contain the information about the deleted rectangles.

Each of these lines contains four integers _x_1, _y_1, _x_2 and _y_2 (1  ≤ _x_1 ≤ _x_2 ≤ n, 1  ≤ _y_1 ≤ _y_2 ≤ n) — the coordinates of the lower left and the upper right cells of a deleted rectangle.

If is guaranteed that the rectangles do not intersect.

第一行包含一个整数 $n$（$1 \leq n \leq 10000$）——棋盘的大小。

第二行包含一个整数 $q$（$0 \leq q \leq 10000$）——被删除的矩形数量。

接下来的 $q$ 行描述了被删除的矩形信息。

每行包含四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$（$1 \leq x_1 \leq x_2 \leq n$，$1 \leq y_1 \leq y_2 \leq n$）——分别表示被删除矩形的左下角单元格与右上角单元格的坐标。

保证这些矩形互不相交。

In the only line print the maximum number of rooks Oleg can place on the board so that no two rooks beat each other.

在唯一的一行中输出 Oleg 能在棋盘上放置的、互不攻击的车（rook）的最大数量。

Here is the board and the example of rooks placement in the first example:

以下是棋盘以及第一个示例中车的摆放方式示意图：