Zoning Restrictions

You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$.

In each spot, if a house has height $a$, you can gain $a^2$ dollars from it.

The city has $m$ zoning restrictions though. The $i$-th restriction says that if the tallest house from spots $l_i$ to $r_i$ is strictly more than $x_i$, you must pay a fine of $c_i$.

You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

Input

The first line contains three integers $n,h,m$ ($1 \leq n,h,m \leq 50$) — the number of spots, the maximum height, and the number of restrictions, respectively.

Each of the next $m$ lines contains four integers $l_i, r_i, x_i, c_i$ ($1 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq h$, $1 \leq c_i \leq 5\,000$).

Output

Print a single integer denoting the maximum profit you can make.

Examples

input

3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000

output

14

input

4 10 2
2 3 8 76
3 4 7 39

output

289

Note

In the first example, it’s optimal to build houses with heights $[1, 3, 2]$. We get a gain of $1^2+3^2+2^2 = 14$. We don’t violate any restrictions, so there are no fees, so the total profit is $14 – 0 = 14$.

In the second example, it’s optimal to build houses with heights $[10, 8, 8, 10]$. We get a gain of $10^2+8^2+8^2+10^2 = 328$, and we violate the second restriction for a fee of $39$, thus the total profit is $328-39 = 289$. Note that even though there isn’t a restriction on building $1$, we must still limit its height to be at most $10$.

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, h, m;
  cin >> n >> h >> m;
flow_graph<int> g(n * h + m + 2, n * h + m, n * h + m + 1);
int ans = 0;
for (int i = 0; i < n; i++) {
    ans += h * h;
    int last = n * h + m;
    for (int j = 0; j < h; j++) {
      g.add(last, i * h + j, h * h - j * j, 0);
      last = i * h + j;
    }
  }
  const int inf = (int) 1e6;
  for (int i = 0; i < m; i++) {
    int l, r, x, c;
    cin >> l >> r >> x >> c;
l--; r--;
if (x == h) {
continue;
}
for (int j = l; j <= r; j++) {
      g.add(j * h + x, n * h + i, inf, 0);
    }
    g.add(n * h + i, n * h + m + 1, c, 0);
  }
  dinic<int> d(g);
ans -= d.max_flow();
cout << ans << '\n';
  return 0;
}