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.
import java.io.*;
import java.util.*;

public class Test {

    static int readInt() {
        int ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    static long readLong() {
        long ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    static String readLine() {
        StringBuilder b = new StringBuilder();
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c != '\r' && c != '\n') {
                    start = true;
                    b.append((char)c);
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return b.toString();
    }

    static PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    class E {
        int v;
        int c;
        int f;
        E(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }

    List<Integer>[] g;
    int src, tgt;
    int[] level;
    int[] que;
    List<E> edges;

    void addEdge(int u, int v, int cap, int rcap) {
        g[u].add(edges.size());
        edges.add(new E(v, cap));
        g[v].add(edges.size());
        edges.add(new E(u, rcap));
    }

    boolean bfs() {
        Arrays.fill(level, -1);
        int a = 0, b = 0;
        que[b++] = src;
        level[src] = 0;
        while (a < b) {
            int u = que[a++];
            for (int i : g[u]) {
                E e = edges.get(i);
                if (e.f < e.c && level[e.v] == -1) {
                    level[e.v] = level[u] + 1;
                    que[b++] = e.v;
                }
            }
        }
        return level[tgt] != -1;
    }

    int send(int u, int f) {
        if (u == tgt) return f;
        int sent = 0;
        for (int i : g[u]) {
            E e = edges.get(i);
            if (level[e.v] == level[u] + 1) {
                int sf = Math.min(e.c - e.f, f);
                if (sf > 0) {
                    sf = send(e.v, sf);
                    E r = edges.get(i ^ 1);
                    e.f += sf;
                    r.f -= sf;
                }
                sent += sf;
                f -= sf;
                if (f == 0) return sent;
            }
        }
        return sent;
    }

    int flow() {
        int f = 0;
        while (bfs()) {
            int s = send(src, Integer.MAX_VALUE);
            f += s;
        }
        return f;
    }


    void start() {
        int n = readInt(), h = readInt(), m = readInt();
        int[] ll = new int[m], rr = new int[m], x = new int[m], c = new int[m];
        for (int i = 0; i < m; i++) {
            ll[i] = readInt() - 1;
            rr[i] = readInt() - 1;
            x[i] = readInt();
            c[i] = readInt();
        }

        src = n*h+m;
        tgt = n*h+m+1;
        g = new List[n*h+m+2];
        for (int i = 0; i < g.length; i++) g[i] = new ArrayList<>();
        edges = new ArrayList<>();
        level = new int[g.length];
        que = new int[g.length];

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += h*h;
            int last = src;
            for (int j = 0; j < h; j++) {
                int u = i*h+j;
                addEdge(last, u, h*h - j*j, 0);
                last = u;
            }
        }

        int inf = 1_000_000;
        for (int i = 0; i < m; i++) {
            if (x[i] == h) continue;
            int u = n*h + i;
            for (int j = ll[i]; j <= rr[i]; j++) {
                int v = j*h + x[i];
                addEdge(v, u, inf, 0);
            }
            addEdge(u, tgt, c[i], 0);
        }

        ans -= flow();
        writer.println(ans);
    }

    public static void main(String[] args) {
        Test te = new Test();
        te.start();
        writer.flush();
    }
}