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.


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

 [Image]

Difficulty: VERY_HARD
Tags: Graph algorithms

Flows and cuts

Starter code:

Solutions:
import sys
from collections import defaultdict

class MaxFlow(object):

	def __init__(self):
		self.edges = defaultdict(lambda : defaultdict(lambda : 0))

	def add_edge(self, u, v, capacity=float('inf')):
		self.edges[u][v] = capacity

	def bfs(self, s, t):
		open_q = [s]
		visited = set()
		parent = dict()
		while open_q:
			close_q = []
			for node in open_q:
				for (v, capacity) in self.edges[node].items():
					if v not in visited and capacity > 0:
						close_q.append(v)
						parent[v] = node
						visited.add(v)
						if v == t:
							result = []
							n2 = v
							n1 = node
							while n1 != s:
								result.append((n1, n2))
								n2 = n1
								n1 = parent[n1]
							result.append((n1, n2))
							return result
			open_q = close_q
		return None

	def solve(self, s, t):
		flow = 0
		route = self.bfs(s, t)
		while route is not None:
			new_flow = float('inf')
			for (_, (n1, n2)) in enumerate(route):
				new_flow = min(new_flow, self.edges[n1][n2])
			for (_, (n1, n2)) in enumerate(route):
				self.edges[n1][n2] -= new_flow
				self.edges[n2][n1] += new_flow
			flow += new_flow
			route = self.bfs(s, t)
		return flow

	def __str__(self):
		result = '{ '
		for (k, v) in self.edges.items():
			result += str(k) + ':' + str(dict(v)) + ', '
		result += '}'
		return result

def main():
	(n, m) = tuple([int(x) for x in input().split()])
	r = []
	xs = set()
	ys = set()
	for i in range(m):
		(x1, y1, x2, y2) = tuple((int(x) for x in input().split()))
		r.append((x1, y1, x2, y2))
		xs.add(x1)
		xs.add(x2 + 1)
		ys.add(y1)
		ys.add(y2 + 1)
	xx = sorted(xs)
	yy = sorted(ys)
	xsize = len(xs)
	ysize = len(ys)
	grid = []
	for i in range(ysize):
		grid.append([False] * xsize)
	for rect in r:
		x1 = rect[0]
		y1 = rect[1]
		x2 = rect[2]
		y2 = rect[3]
		for (i, y) in enumerate(yy):
			for (j, x) in enumerate(xx):
				if x1 <= x and y1 <= y and (x2 >= x) and (y2 >= y):
					grid[i][j] = True
	f = MaxFlow()
	for i in range(len(yy)):
		for j in range(len(xx)):
			if grid[i][j]:
				f.add_edge(1 + i, len(yy) + 1 + j, float('inf'))
	for i in range(len(yy) - 1):
		f.add_edge(0, i + 1, yy[i + 1] - yy[i])
	for i in range(len(xx) - 1):
		f.add_edge(len(yy) + 1 + i, len(xx) + len(yy) + 1, xx[i + 1] - xx[i])
	print(f.solve(0, len(xx) + len(yy) + 1))
main()