#include <bits/stdc++.h>
using namespace std;
const int N = 3005, M = 300005;
bool vis[N];
int nn, tong[55][55], q, n, m, nedge, oo = 1000000005, last[N], son[N], ed[M],
                                      nextt[M], di[M], que[N], laedge[N],
                                      dist[N], cost[M];
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(int a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(int a) {
  write(a);
  puts("");
}
inline bool spfa(int s, int t) {
  for (int i = 1; i <= n; i++) {
    dist[i] = oo;
    last[i] = laedge[i] = vis[i] = que[i - 1] = 0;
  }
  int tot = 1, l = 0, r = 0;
  que[0] = s;
  vis[s] = true;
  dist[s] = 0;
  while (tot) {
    int k = que[l];
    vis[k] = false;
    if (++l == n) l = 0;
    tot--;
    for (int i = son[k]; i; i = nextt[i]) {
      if (di[i] > 0 && dist[ed[i]] > dist[k] + cost[i]) {
        dist[ed[i]] = dist[k] + cost[i];
        laedge[ed[i]] = i;
        last[ed[i]] = k;
        if (vis[ed[i]] == 0) {
          if (++r == n) r = 0;
          que[r] = ed[i];
          tot++;
          vis[ed[i]] = true;
        }
      }
    }
  }
  return last[t] > 0;
}
inline int costflow(int s, int t) {
  int sum = 0, cost = 0;
  while (spfa(s, t)) {
    int mmin = oo;
    for (int i = t; last[i]; i = last[i]) {
      mmin = min(mmin, di[laedge[i]]);
    }
    sum += mmin;
    cost += dist[t] * mmin;
    for (int i = t; last[i]; i = last[i]) {
      di[laedge[i]] -= mmin;
      di[(1 ^ (laedge[i] - 1)) + 1] += mmin;
    }
  }
  if (sum != nn)
    return -1;
  else
    return cost;
}
inline void aedge(int a, int b, int c, int d) {
  nextt[++nedge] = son[a];
  son[a] = nedge;
  ed[nedge] = b;
  di[nedge] = c;
  cost[nedge] = d;
}
int main() {
  nn = n = read();
  q = read();
  while (q--) {
    int s1 = read(), l = read(), r = read(), s2 = read();
    if (s1 == 1) {
      for (int i = 1; i < s2; i++)
        for (int j = l; j <= r; j++) tong[j][i] = 1;
    } else {
      for (int i = s2 + 1; i <= n; i++)
        for (int j = l; j <= r; j++) tong[j][i] = 1;
    }
  }
  int s = n + n * n + n + 1, t = s + 1;
  for (int i = 1; i <= n; i++) {
    aedge(s, i, n, 0);
    aedge(i, s, 0, 0);
    aedge(n + n * n + i, t, 1, 0);
    aedge(t, n + n * n + i, 0, 0);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      aedge(i, i * n + j, 1, j * 2 - 1);
      aedge(i * n + j, i, 0, 1 - 2 * j);
      for (int k = 1; k <= n; k++)
        if (!tong[k][i]) {
          aedge(i * n + j, n + n * n + k, 1, 0);
          aedge(n + n * n + k, i * n + j, 0, 0);
        }
    }
  }
  n = t;
  cout << (costflow(s, t)) << endl;
}
