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 maxN = 3004;
long long INF = 1ll << 44;
vector<int> G[maxN];
long long cap[maxN][maxN];
int mp[maxN][maxN];
struct Max_flow {
  vector<int>* G;
  int source, target, bfsctr, parent[maxN], vis[maxN], Q[maxN];
  bool bfs() {
    vis[source] = ++bfsctr;
    Q[0] = source;
    for (int qF = 0, qB = 1; qF != qB; qF++) {
      int v = Q[qF];
      for (int u : G[v]) {
        if (vis[u] == bfsctr or cap[v][u] <= 0) continue;
        vis[u] = bfsctr;
        parent[u] = v;
        Q[qB++] = u;
        if (u == target) {
          qF = qB - 1;
          break;
        }
      }
    }
    return vis[target] == bfsctr;
  }
  long long maxflow(vector<int>* Gin, int n, int src, int trg) {
    G = Gin;
    source = src;
    target = trg;
    long long res = 0;
    while (bfs()) {
      long long mc = INF;
      for (int v = target; v != source; v = parent[v])
        mc = min(mc, cap[parent[v]][v]);
      for (int v = target; v != source; v = parent[v])
        cap[parent[v]][v] -= mc, cap[v][parent[v]] += mc;
      res += mc;
    }
    return res;
  }
} alg;
void conn(int a, int b, long long c) {
  G[a].push_back(b);
  G[b].push_back(a);
  cap[a][b] = c;
}
int main() {
  int n, H, m;
  scanf("%d%d%d", &n, &H, &m);
  int num = 0;
  for (int i = (1); i < (n + 1); i++)
    for (int h = (0); h < (H + 1); h++) mp[i][h] = ++num;
  int src = ++num, trg = ++num;
  for (int i = (1); i < (n + 1); i++) {
    conn(src, mp[i][0], H * H);
    for (int h = (0); h < (H); h++)
      conn(mp[i][h], mp[i][h + 1], H * H - (h + 1) * (h + 1));
    conn(mp[i][H], trg, INF);
  }
  while (m--) {
    int a, b, x, c, v = ++num;
    scanf("%d%d%d%d", &a, &b, &x, &c);
    for (int i = (a); i < (b + 1); i++) conn(mp[i][x], v, INF);
    conn(v, trg, c);
  }
  printf("%lld\n", 1ll * n * H * H - alg.maxflow(G, num, src, trg));
  return 0;
}
