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 ≤ n,h,m ≤ 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 ≤ l_i ≤ r_i ≤ n, 0 ≤ x_i ≤ h, 1 ≤ c_i ≤ 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.
#include <bits/stdc++.h>
using namespace std;
static const int Maxn = 2700;
static const int inf = 0x3f3f3f3f;
namespace HLPP {
struct edge {
  int to, flow, next;
  edge(int to, int flow, int next) : to(to), flow(flow), next(next) {}
};
vector<edge> a[Maxn];
vector<int> list[Maxn], h, cnt, que, e;
vector<std ::list<int>::iterator> iter;
std ::list<int> dlist[Maxn];
int hst, nowh;
inline void clear() {
  for (int i = 0; i < Maxn; ++i) a[i].clear();
  iter.clear();
}
inline void add_edge(int u, int v, int f) {
  a[u].push_back(edge(v, f, (int)a[v].size()));
  a[v].push_back(edge(u, 0, (int)a[u].size() - 1));
}
inline void relabel(int n, int t) {
  h.assign(n, n);
  h[t] = 0;
  cnt.assign(n, 0);
  que.clear();
  que.resize(n + 1);
  int qh = 0, qt = 0;
  for (que[qt++] = t; qh < qt;) {
    int u = que[qh++], het = h[u] + 1;
    for (vector<edge>::iterator p = a[u].begin(); p != a[u].end(); ++p)
      if (h[p->to] == n && a[p->to][p->next].flow > 0)
        cnt[h[p->to] = het]++, que[qt++] = p->to;
  }
  for (register int i = 0; i <= n; ++i) list[i].clear(), dlist[i].clear();
  for (register int u = 0; u < n; ++u) {
    if (h[u] < n) {
      iter[u] = dlist[h[u]].insert(dlist[h[u]].begin(), u);
      if (e[u] > 0) list[h[u]].push_back(u);
    }
  }
  hst = (nowh = h[que[qt - 1]]);
}
inline void push(int u, edge &ed) {
  int v = ed.to;
  int df = min(e[u], ed.flow);
  ed.flow -= df;
  a[v][ed.next].flow += df;
  e[u] -= df, e[v] += df;
  if (0 < e[v] && e[v] <= df) list[h[v]].push_back(v);
}
inline void push(int n, int u) {
  int nh = n;
  for (vector<edge>::iterator p = a[u].begin(); p != a[u].end(); ++p) {
    if (p->flow > 0) {
      if (h[u] == h[p->to] + 1) {
        push(u, *p);
        if (!e[u]) return;
      } else
        nh = min(nh, h[p->to] + 1);
    }
  }
  int het = h[u];
  if (cnt[het] == 1) {
    for (register int i = het; i <= hst; ++i) {
      for (std ::list<int>::iterator it = dlist[i].begin();
           it != dlist[i].end(); ++it)
        cnt[h[*it]]--, h[*it] = n;
      dlist[i].clear();
    }
    hst = het - 1;
  } else {
    cnt[het]--;
    iter[u] = dlist[het].erase(iter[u]);
    h[u] = nh;
    if (nh == n) return;
    cnt[nh]++;
    iter[u] = dlist[nh].insert(dlist[nh].begin(), u);
    hst = max(hst, nowh = nh);
    list[nh].push_back(u);
  }
}
int hlpp(int n, int s, int t) {
  ++n;
  if (s == t) return 0;
  nowh = hst = 0;
  h.assign(n, 0), h[s] = n;
  iter.resize(n);
  for (register int i = 0; i < n; ++i)
    if (i != s) iter[i] = dlist[h[i]].insert(dlist[h[i]].begin(), i);
  cnt.assign(n, 0);
  cnt[0] = n - 1;
  e.assign(n, 0), e[s] = INT_MAX, e[t] = -INT_MAX;
  for (register int i = 0; i < (int)a[s].size(); ++i) push(s, a[s][i]);
  relabel(n, t);
  for (int u; nowh >= 0;) {
    if (list[nowh].empty()) {
      nowh--;
      continue;
    }
    u = list[nowh].back();
    list[nowh].pop_back();
    push(n, u);
  }
  return e[t] + INT_MAX;
}
}  // namespace HLPP
int n, h, m, S, T;
inline int get_id(int x, int y) { return (x - 1) * (h + 2) + y + 1; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  cout << fixed << setprecision(12);
  cin >> n >> h >> m;
  S = 2601, T = 2602;
  int extra = T + 1;
  for (int i = 1; i <= n; ++i) {
    HLPP::add_edge(S, get_id(i, 0), inf);
    HLPP::add_edge(get_id(i, h + 1), T, inf);
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= h; ++j)
      HLPP::add_edge(get_id(i, j), get_id(i, j + 1), h * h - j * j);
  for (int i = 1; i <= m; ++i) {
    int l, r, x, c;
    cin >> l >> r >> x >> c;
    HLPP::add_edge(extra, T, c);
    for (int j = l; j <= r; ++j) HLPP::add_edge(get_id(j, x + 1), extra, inf);
    ++extra;
  }
  printf("%d\n", n * h * h - HLPP::hlpp(extra, S, T));
  return 0;
}
