#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int tot = 1, head[5010], pre[5010], last[5010], vis[5010], n, m, S, T;
long long flow[5010], maxflow, mincost, dis[5010];
struct edge {
  int to, next;
  long long flow, cost;
} dat[200001];
void add_edge(int x, int y, long long z, long long w) {
  dat[++tot] = (edge){y, head[x], z, w};
  head[x] = tot;
}
void Add_edge(int x, int y, long long z, long long w) {
  add_edge(x, y, z, w);
  add_edge(y, x, 0, -w);
}
long long spfa() {
  q.push(S);
  for (int i = 0; i <= 2 * n + 1; i++) dis[i] = flow[i] = 1e18, vis[i] = 0;
  dis[S] = 0, pre[T] = -1;
  while (!q.empty()) {
    int x = q.front();
    vis[x] = 0;
    q.pop();
    for (int i = head[x]; i; i = dat[i].next) {
      int t = dat[i].to;
      if (dat[i].flow > 0 && dis[t] > dis[x] + dat[i].cost) {
        flow[t] = min(dat[i].flow, flow[x]);
        dis[t] = dis[x] + dat[i].cost;
        last[t] = i;
        pre[t] = x;
        if (!vis[t]) {
          vis[t] = 1;
          q.push(t);
        }
      }
    }
  }
  if (pre[T] == -1) return 0;
  return 1;
}
void MCMF() {
  while (spfa()) {
    maxflow += flow[T];
    mincost += flow[T] * dis[T];
    long long now = T;
    while (now != S) {
      dat[last[now]].flow -= flow[T];
      dat[last[now] ^ 1].flow += flow[T];
      now = pre[now];
    }
  }
}
int minn[5010], maxx[5010];
int main() {
  cin >> n >> m;
  S = 0, T = 2 * n + 1;
  for (int i = 1; i <= n; i++) maxx[i] = n, minn[i] = 1;
  for (int i = 1; i <= m; i++) {
    int typ, l, r, v;
    scanf("%d%d%d%d", &typ, &l, &r, &v);
    for (int j = l; j <= r; j++) {
      if (typ == 1)
        minn[j] = max(minn[j], v);
      else
        maxx[j] = min(maxx[j], v);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) Add_edge(S, i, 1, j * j - (j - 1) * (j - 1));
  }
  for (int i = 1; i <= n; i++) {
    for (int j = minn[i]; j <= maxx[i]; j++) Add_edge(j, i + n, 1, 0);
    Add_edge(i + n, T, 1, 0);
  }
  MCMF();
  if (maxflow != n)
    puts("-1");
  else
    cout << mincost;
}
