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;
inline long long read() {
  char ch = getchar();
  int s = 0, w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * w;
}
struct edge {
  int next, to, fl;
} e[1000010 << 1];
int head[1000010], cnt = 1;
int depth[1000010];
queue<int> Q;
int ans, dcnt;
int n, h, m;
int s, t;
inline void add_edge(int from, int to, int fl) {
  e[++cnt].to = to;
  e[cnt].next = head[from];
  e[cnt].fl = fl;
  head[from] = cnt;
}
inline int bfs() {
  memset(depth, 0, sizeof(depth));
  while (!Q.empty()) Q.pop();
  Q.push(s);
  depth[s] = 1;
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (register int i = head[x]; i; i = e[i].next) {
      if (e[i].fl && !depth[e[i].to])
        depth[e[i].to] = depth[x] + 1, Q.push(e[i].to);
    }
  }
  return depth[t];
}
int dfs(int now, int flow) {
  if (now == t) return flow;
  int ret = 0;
  for (register int i = head[now]; i; i = e[i].next) {
    if (ret == flow) return ret;
    if (depth[e[i].to] == depth[now] + 1 && e[i].fl) {
      int fl = dfs(e[i].to, min(e[i].fl, flow - ret));
      if (fl) {
        ret += fl;
        e[i].fl -= fl;
        e[i ^ 1].fl += fl;
      }
    }
  }
  if (!ret) depth[now] = 0;
  return ret;
}
inline int Dinic() {
  int sum = 0;
  while (bfs()) {
    while (int x = dfs(s, 0x7fffffff / 2)) sum += x;
  }
  return sum;
}
inline int idx(int x, int y) { return (x - 1) * (h + 2) + y; }
int main() {
  n = read(), h = read(), m = read();
  t = 1000010 - 10;
  for (register int i = 1; i <= n; i++) ans += h * h;
  for (register int i = 1; i <= n; i++) {
    for (register int j = 1; j <= h + 1; j++)
      add_edge(idx(i, j), idx(i, j + 1), h * h - (j - 1) * (j - 1)),
          add_edge(idx(i, j + 1), idx(i, j), 0);
  }
  dcnt = n * (h + 2);
  for (register int i = 1; i <= n; i++) {
    add_edge(s, idx(i, 1), 0x7fffffff / 2);
    add_edge(idx(i, 1), s, 0);
    add_edge(idx(i, h + 2), t, 0x7fffffff / 2);
    add_edge(t, idx(i, h + 2), 0);
  }
  for (register int i = 1; i <= m; i++) {
    int l = read(), r = read(), H = read(), val = read();
    if (H == h) continue;
    ++dcnt;
    add_edge(dcnt, t, val);
    add_edge(t, dcnt, 0);
    for (register int j = l; j <= r; j++) {
      add_edge(idx(j, H + 2), dcnt, 0x7fffffff / 2);
      add_edge(dcnt, idx(j, H + 2), 0);
    }
  }
  printf("%d\n", ans - Dinic());
  return 0;
}
