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;
const int INF = 0x3f3f3f3f;
const int N = 10010, M = 2e5 + 10;
struct node {
  long long v, f, nxt;
} e[M << 2];
int n, m, s, t, Enum = 1;
int front[N], cur[N], deep[N], num[N], pre[N];
long long q[N], a[N];
inline void add(int u, int v, int w) {
  e[++Enum].v = v;
  e[Enum].f = w;
  e[Enum].nxt = front[u];
  front[u] = Enum;
  e[++Enum].v = u;
  e[Enum].f = 0;
  e[Enum].nxt = front[v];
  front[v] = Enum;
}
void bfs(int t) {
  for (int i = 1; i <= n; i++) deep[i] = n;
  deep[t] = 0;
  int head = 1, tail = 0, u, v;
  q[++tail] = t;
  while (head <= tail) {
    u = q[head++];
    for (int i = front[u]; i; i = e[i].nxt) {
      v = e[i].v;
      if (deep[v] == n && e[i ^ 1].f) {
        deep[v] = deep[u] + 1;
        q[++tail] = v;
      }
    }
  }
}
long long Augment(int s, int t) {
  long long flow = INF;
  for (int i = t; i != s; i = e[pre[i] ^ 1].v) flow = min(flow, e[pre[i]].f);
  for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
    e[pre[i]].f -= flow;
    e[pre[i] ^ 1].f += flow;
  }
  return flow;
}
long long ISAP(int s, int t) {
  int x = s;
  long long maxflow = 0;
  bfs(t);
  for (int i = 1; i <= n; i++) {
    num[deep[i]]++;
    cur[i] = front[i];
  }
  while (deep[s] < n) {
    if (x == t) maxflow += Augment(s, t), x = s;
    bool flag = 0;
    for (int i = cur[x]; i; i = e[i].nxt) {
      int v = e[i].v;
      if (deep[x] == deep[v] + 1 && e[i].f) {
        flag = 1;
        pre[v] = i;
        cur[x] = i;
        x = v;
        break;
      }
    }
    if (!flag) {
      int mins = n - 1;
      for (int i = front[x]; i; i = e[i].nxt)
        if (e[i].f) mins = min(mins, deep[e[i].v]);
      num[deep[x]]--;
      if (!num[deep[x]]) break;
      num[deep[x] = mins + 1]++;
      cur[x] = front[x];
      if (x != s) x = e[pre[x] ^ 1].v;
    }
  }
  return maxflow;
}
int nn, h, c[55];
int get(int i, int j) { return nn + 1 + (h + 1) * (i - 1) + j; }
int main() {
  long long ans = 0, sum = 0;
  scanf("%d%d%d", &nn, &h, &m);
  for (int i = 1; i <= h; i++) {
    sum += i * i;
  }
  n = nn * (h + 2);
  for (int i = 1; i <= nn; i++) {
    add(i, get(i, 0), 1e9);
    for (int j = 0; j < h; j++) {
      add(get(i, j), get(i, j + 1), sum - j * j);
    }
  }
  for (int i = 1; i <= m; i++) {
    int l, r, x;
    scanf("%d%d%d%d", &l, &r, &x, &c[i]);
    for (int j = l; j <= r; j++) {
      if (x + 1 <= h) add(get(j, x + 1), n + i, 1e9);
    }
  }
  s = n + m + 1, t = n + m + 2;
  for (int i = 1; i <= nn; i++) {
    add(s, i, 1e9);
    add(get(i, h), t, sum - h * h);
  }
  for (int i = 1; i <= m; i++) {
    add(n + i, t, c[i]);
  }
  n += m + 2;
  printf("%lld", sum * nn - ISAP(s, t));
  return 0;
}
