Problem: There is a square grid of size n × 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 × 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 ≤ n ≤ 10^{9}, 0 ≤ m ≤ 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 ≤ x_{i1} ≤ x_{i2} ≤ n, 1 ≤ y_{i1} ≤ y_{i2} ≤ 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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long pr[1001010];
long long inv[1001010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = (pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = inv[i + 1] * (i + 1) % mod;
  }
}
struct edge {
  long long to, cap, num, moto;
};
vector<edge> ZANYO[100020];
long long label[100020];
queue<pair<long long, long long> > qu_bfs;
long long dokomade[100020];
void add_edge(long long s_point, long long t_point, long long capa) {
  ZANYO[s_point].push_back(
      (edge){t_point, capa, (long long)ZANYO[t_point].size(), 0});
  ZANYO[t_point].push_back(
      (edge){s_point, 0, (long long)ZANYO[s_point].size() - 1, 1});
}
void bfs_dinic(long long s_point, long long N) {
  for (long long i = 0; i < N; i++) label[i] = -1;
  while (qu_bfs.size()) qu_bfs.pop();
  qu_bfs.push(make_pair(s_point, 0));
  while (qu_bfs.size()) {
    pair<long long, long long> z = qu_bfs.front();
    qu_bfs.pop();
    if (label[z.first] >= 0) continue;
    label[z.first] = z.second;
    for (auto &v : ZANYO[z.first]) {
      if (v.cap == 0) continue;
      if (v.cap < 0) {
        cout << "error" << endl;
        exit(0);
      }
      if (label[v.to] >= 0) continue;
      qu_bfs.push(make_pair(v.to, z.second + 1));
    }
  }
  return;
}
long long dfs_dinic(long long s_point, long long t_point, long long ima_flow) {
  if (s_point == t_point) return ima_flow;
  while (1) {
    if (dokomade[s_point] >= ZANYO[s_point].size()) break;
    long long edanum = dokomade[s_point];
    if (ZANYO[s_point][edanum].cap < 0) {
      cout << "minus" << endl;
      exit(0);
    }
    if (ZANYO[s_point][edanum].cap <= 0 ||
        label[s_point] + 1 != label[ZANYO[s_point][edanum].to]) {
      dokomade[s_point]++;
      continue;
    }
    long long W = dfs_dinic(ZANYO[s_point][edanum].to, t_point,
                            min(ZANYO[s_point][edanum].cap, ima_flow));
    if (W > 0) {
      ZANYO[s_point][edanum].cap -= W;
      ZANYO[ZANYO[s_point][edanum].to][ZANYO[s_point][edanum].num].cap += W;
      return W;
    }
    dokomade[s_point]++;
  }
  return 0;
}
long long max_flow_dinic(long long s_point, long long t_point, long long N) {
  long long jougen = 1000000007 * 1000000000ll;
  long long ans_flow = 0;
  while (1) {
    bfs_dinic(s_point, N);
    if (label[t_point] == -1) break;
    for (long long i = 0; i < N; i++) dokomade[i] = 0;
    while (1) {
      long long ima_flow = dfs_dinic(s_point, t_point, jougen + 1);
      if (ima_flow == 0) break;
      ans_flow += ima_flow;
    }
  }
  return ans_flow;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<pa4> ve;
  long long n, q;
  cin >> n >> q;
  set<long long> sex, sey;
  sex.insert(0);
  sex.insert(n);
  sey.insert(0);
  sey.insert(n);
  for (long long i = 0; i < q; i++) {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--, y1--;
    sex.insert(x1);
    sex.insert(x2);
    sey.insert(y1);
    sey.insert(y2);
    ve.push_back((pa4){x1, x2, y1, y2});
  }
  vector<long long> vx, vy;
  for (auto it = sex.begin(); it != sex.end(); it++) vx.push_back(*it);
  for (auto it = sey.begin(); it != sey.end(); it++) vy.push_back(*it);
  long long a = vx.size() - 1;
  long long b = vy.size() - 1;
  set<pair<long long, long long> > se;
  for (long long i = 0; i < a; i++)
    for (long long j = 0; j < b; j++) {
      long long sx = vx[i], sy = vx[i + 1];
      long long tx = vy[j], ty = vy[j + 1];
      bool bo = 0;
      for (auto v : ve) {
        if (sx >= v.x && v.y >= sy && tx >= v.z && v.w >= ty) bo = 1;
      }
      if (bo) se.insert(make_pair(i, j));
    }
  long long A[200], B[200];
  for (long long i = 0; i < a; i++) {
    long long sx = vx[i], sy = vx[i + 1];
    add_edge(0, 1 + i, sy - sx);
    A[i] = sy - sx;
  }
  for (long long j = 0; j < b; j++) {
    long long tx = vy[j], ty = vy[j + 1];
    add_edge(a + 1 + j, a + b + 1, ty - tx);
    B[j] = ty - tx;
  }
  for (auto it = se.begin(); it != se.end(); it++) {
    pair<long long, long long> z = *it;
    add_edge(1 + z.first, a + 1 + z.second, min(A[z.first], B[z.second]));
  }
  cout << max_flow_dinic(0, a + b + 1, a + b + 5) << endl;
  return 0;
}