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.

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.

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class flow_graph {
public:
static constexpr T eps = (T) 1e-9;

struct edge {
int from;
int to;
T c;
T f;
};

vector<vector<int>> g;
vector<edge> edges;
int n;
int st;
int fin;
T flow;

flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {
assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    flow = 0;
  }

  void clear_flow() {
    for (const edge &e : edges) {
      e.f = 0;
    }
    flow = 0;
  }

  int add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, forward_cap, 0});
    g[to].push_back(id + 1);
    edges.push_back({to, from, backward_cap, 0});
    return id;
  }
};

template <typename T>
class dinic {
public:
flow_graph<T> &g;

vector<int> ptr;
vector<int> d;
vector<int> q;

dinic(flow_graph<T> &_g) : g(_g) {
ptr.resize(g.n);
d.resize(g.n);
q.resize(g.n);
}

bool expath() {
fill(d.begin(), d.end(), -1);
q[0] = g.fin;
d[g.fin] = 0;
int beg = 0, end = 1;
while (beg < end) {
      int i = q[beg++];
      for (int id : g.g[i]) {
        const auto &e = g.edges[id];
        const auto &back = g.edges[id ^ 1];
        if (back.c - back.f > g.eps && d[e.to] == -1) {
d[e.to] = d[i] + 1;
if (e.to == g.st) {
return true;
}
q[end++] = e.to;
}
}
}
return false;
}

T dfs(int v, T w) {
if (v == g.fin) {
return w;
}
int &j = ptr[v];
while (j >= 0) {
int id = g.g[v][j];
const auto &e = g.edges[id];
if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) {
T t = dfs(e.to, min(e.c - e.f, w));
if (t > g.eps) {
g.edges[id].f += t;
g.edges[id ^ 1].f -= t;
return t;
}
}
j--;
}
return 0;
}

T max_flow() {
while (expath()) {
for (int i = 0; i < g.n; i++) {
        ptr[i] = (int) g.g[i].size() - 1;
      }
      T big_add = 0;
      while (true) {
        T add = dfs(g.st, numeric_limits<T>::max());
if (add <= g.eps) {
          break;
        }
        big_add += add;
      }
      if (big_add <= g.eps) {
        break;
      }
      g.flow += big_add;
    }
    return g.flow;
  }

  vector<bool> min_cut() {
max_flow();
vector<bool> ret(g.n);
for (int i = 0; i < g.n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
vector<int> xa(m), ya(m), xb(m), yb(m);
vector<int> xs = {0, n};
vector<int> ys = {0, n};
for (int i = 0; i < m; i++) {
    cin >> xa[i] >> ya[i] >> xb[i] >> yb[i];
--xa[i]; --ya[i];
xs.push_back(xa[i]);
ys.push_back(ya[i]);
xs.push_back(xb[i]);
ys.push_back(yb[i]);
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
int nx = (int) xs.size() - 1;
int ny = (int) ys.size() - 1;
const long long inf = (long long) 2e18;
flow_graph<long long> g(nx + ny + 2, nx + ny, nx + ny + 1);
for (int i = 0; i < nx; i++) {
    g.add(nx + ny, i, xs[i + 1] - xs[i], 0);
  }
  for (int i = 0; i < ny; i++) {
    g.add(nx + i, nx + ny + 1, ys[i + 1] - ys[i], 0);
  }
  for (int i = 0; i < nx; i++) {
    for (int j = 0; j < ny; j++) {
      int ok = 0;
      for (int k = 0; k < m; k++) {
        if (xa[k] <= xs[i] && xs[i + 1] <= xb[k] && ya[k] <= ys[j] && ys[j + 1] <= yb[k]) {
          ok = 1;
          break;
        }
      }
      if (ok) {
        g.add(i, nx + j, inf, 0);
      }
    }
  }
  dinic<long long> d(g);
cout << d.max_flow() << '\n';
  return 0;
}