Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Rectangle Painting 2

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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.

Output

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

Examples

Input

10 2 4 1 5 10 1 4 10 5

Output

4

Input

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

Output

3

Note

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/24/2020 21:29:57 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|