#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
struct MinCostFlow {
  const static int MaxFlow = numeric_limits<int>::max();
  bool iszerocap(int cap) { return cap == 0; }
  struct edge {
    int target;
    int cost;
    int residual_capacity;
    int orig_capacity;
    size_t revid;
  };
  int n;
  vector<vector<edge>> graph;
  vector<int> pi;
  bool needNormalize, ranbefore;
  int lastStart;
  MinCostFlow(int n)
      : graph(n), n(n), pi(n, 0), needNormalize(false), ranbefore(false) {}
  void addEdge(int s, int e, int cost, int cap) {
    if (s == e) return;
    edge forward = {e, cost, cap, cap, graph[e].size()};
    edge backward = {s, -cost, 0, 0, graph[s].size()};
    if (cost < 0 || ranbefore) needNormalize = true;
    graph[s].emplace_back(forward);
    graph[e].emplace_back(backward);
  }
  bool normalize(int s) {
    auto infinite_cost = numeric_limits<int>::max();
    vector<int> dist(n, infinite_cost);
    dist[s] = 0;
    queue<int> q;
    vector<int> v(n), relax_count(n);
    v[s] = 1;
    q.push(s);
    while (!q.empty()) {
      int cur = q.front();
      v[cur] = 0;
      q.pop();
      if (++relax_count[cur] >= n) return false;
      for (const auto &e : graph[cur]) {
        if (iszerocap(e.residual_capacity)) continue;
        auto next = e.target;
        auto ncost = dist[cur] + e.cost;
        if (dist[next] > ncost) {
          dist[next] = ncost;
          if (v[next]) continue;
          v[next] = 1;
          q.push(next);
        }
      }
    }
    for (int i = 0; i < n; i++) pi[i] = dist[i];
    return true;
  }
  pair<int, int> AugmentShortest(int s, int e, int flow_limit) {
    auto infinite_cost = numeric_limits<int>::max();
    auto infinite_flow = numeric_limits<int>::max();
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pq;
    vector<pair<int, int>> dist(n, pair<int, int>(infinite_cost, 0));
    vector<int> from(n, -1), v(n);
    if (needNormalize || (ranbefore && lastStart != s)) normalize(s);
    ranbefore = true;
    lastStart = s;
    dist[s] = pair<int, int>(0, infinite_flow);
    pq.emplace(dist[s].first, s);
    while (!pq.empty()) {
      auto cur = pq.top().second;
      pq.pop();
      if (v[cur]) continue;
      v[cur] = 1;
      if (cur == e) continue;
      for (const auto &e : graph[cur]) {
        auto next = e.target;
        if (v[next]) continue;
        if (iszerocap(e.residual_capacity)) continue;
        auto ncost = dist[cur].first + e.cost - pi[next] + pi[cur];
        auto nflow = min(dist[cur].second, e.residual_capacity);
        if (dist[next].first <= ncost) continue;
        dist[next] = make_pair(ncost, nflow);
        from[next] = e.revid;
        pq.emplace(dist[next].first, next);
      }
    }
    auto p = e;
    auto pathcost = dist[p].first + pi[p] - pi[s];
    auto flow = dist[p].second;
    if (iszerocap(flow) || (flow_limit <= 0 && pathcost >= 0))
      return pair<int, int>(0, 0);
    if (flow_limit > 0) flow = min(flow, flow_limit);
    for (int i = 0; i < n; i++) {
      if (iszerocap(dist[i].second)) continue;
      pi[i] += dist[i].first;
    }
    while (from[p] != -1) {
      auto nedge = from[p];
      auto np = graph[p][nedge].target;
      auto fedge = graph[p][nedge].revid;
      graph[p][nedge].residual_capacity += flow;
      graph[np][fedge].residual_capacity -= flow;
      p = np;
    }
    return make_pair(pathcost * flow, flow);
  }
  pair<int, int> solve(int s, int e, int flow_minimum = MaxFlow) {
    int total_cost = 0;
    int total_flow = 0;
    for (;;) {
      auto res = AugmentShortest(s, e, flow_minimum - total_flow);
      if (res.second <= 0) break;
      total_cost += res.first;
      total_flow += res.second;
    }
    return pair<int, int>(total_cost, total_flow);
  }
};
int mini[MAXN];
int maxi[MAXN];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, a, b, c, d;
  cin >> n >> m;
  int s = n + n, t = s + 1;
  MinCostFlow g(n + n + 2);
  for (int i = 0; i < n; i++) {
    mini[i] = 0;
    maxi[i] = n - 1;
  }
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c >> d;
    d--;
    b--, c--;
    if (a == 1)
      for (int i = b; i <= c; i++) mini[i] = max(mini[i], d);
    else
      for (int i = b; i <= c; i++) maxi[i] = min(maxi[i], d);
  }
  for (int i = 0; i < n; i++) g.addEdge(s, i, 0, 1);
  for (int i = 0; i < n; i++)
    for (int j = mini[i]; j <= maxi[i]; j++) g.addEdge(i, j + n, 0, 1);
  for (int i = 0; i < n; i++)
    for (int j = 1; j <= n; j++)
      g.addEdge(i + n, t, j * j - (j - 1) * (j - 1), 1);
  pair<int, int> ans = g.solve(s, t);
  if (ans.second == n)
    cout << ans.first << '\n';
  else
    cout << -1 << '\n';
  return 0;
}
