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.
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

        public class MaxFlowDinic { // O(V^2 * E)
            List<Edge>[] graph;
            public MaxFlowDinic(int nodes) {
                graph = createGraph(nodes);
            }

            class Edge {
                int t, rev, cap, f;

                public Edge(int t, int rev, int cap) {
                    this.t = t;
                    this.rev = rev;
                    this.cap = cap;
                }
            }

            public List<Edge>[] createGraph(int nodes) {
                List<Edge>[] graph = new List[nodes];
                for (int i = 0; i < nodes; i++)
                    graph[i] = new ArrayList<>();
                return graph;
            }

            public void addEdge(int s, int t, int cap) {
                graph[s].add(new Edge(t, graph[t].size(), cap));
                graph[t].add(new Edge(s, graph[s].size() - 1, 0));
            }

            boolean dinicBfs(int src, int dest, int[] dist) {
                Arrays.fill(dist, -1);
                dist[src] = 0;
                int[] Q = new int[graph.length];
                int sizeQ = 0;
                Q[sizeQ++] = src;
                for (int i = 0; i < sizeQ; i++) {
                    int u = Q[i];
                    for (Edge e : graph[u]) {
                        if (dist[e.t] < 0 && e.f < e.cap) {
                            dist[e.t] = dist[u] + 1;
                            Q[sizeQ++] = e.t;
                        }
                    }
                }
                return dist[dest] >= 0;
            }

            int dinicDfs(int[] ptr, int[] dist, int dest, int u, int f) {
                if (u == dest)
                    return f;
                for (; ptr[u] < graph[u].size(); ++ptr[u]) {
                    Edge e = graph[u].get(ptr[u]);
                    if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
                        int df = dinicDfs(ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
                        if (df > 0) {
                            e.f += df;
                            graph[e.t].get(e.rev).f -= df;
                            return df;
                        }
                    }
                }
                return 0;
            }

            public int maxFlow(int src, int dest) {
                int flow = 0;
                int[] dist = new int[graph.length];
                while (dinicBfs(src, dest, dist)) {
                    int[] ptr = new int[graph.length];
                    while (true) {
                        int df = dinicDfs(ptr, dist, dest, src, Integer.MAX_VALUE);
                        if (df == 0)
                            break;
                        flow += df;
                    }
                }
                return flow;
            }
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int inf = Integer.MAX_VALUE / 2;
            int n = sc.nextInt();
            int h = sc.nextInt();
            int m = sc.nextInt();
            int cost = n * h * h;
            int start = n * (h + 1) + m;
            MaxFlowDinic md = new MaxFlowDinic(2 + n * (h + 1) + m);
            for (int i = 0; i < n; i++) {
                md.addEdge(start, i * (h + 1), inf);
                for (int j = 0; j < h; j++) {
                    md.addEdge(i * (h + 1) + j, i * (h + 1) + j + 1, h * h - j * j);
                }
            }
            for (int t = 0; t < m; t++) {
                int l = sc.nextInt() - 1;
                int r = sc.nextInt();
                int x = sc.nextInt();
                int c = sc.nextInt();
                if (x == h) continue;
                for (int i = l; i < r; i++) {
                    md.addEdge(i * (h + 1) + x + 1, n * (h + 1) + t, inf);
                }
                md.addEdge(n * (h + 1) + t, start + 1, c);
            }
            int mc = md.maxFlow(start, start + 1);
            pw.println(cost - mc);
        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));

//        createTestCases();
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}