Problem: 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 will gain a^2 dollars from it.

The city has m zoning restrictions. The i-th restriction says that the tallest house from spots l_i to r_i (inclusive) must be at most x_i.

You would like to build houses to maximize your profit. Determine the maximum profit possible.

Input

The first line contains three integers n, h, and m (1 ≤ n,h,m ≤ 50) — the number of spots, the maximum height, and the number of restrictions.

Each of the next m lines contains three integers l_i, r_i, and x_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ x_i ≤ h) — left and right limits (inclusive) of the i-th restriction and the maximum possible height in that range.

Output

Print a single integer, the maximum profit you can make.

Examples

Input


3 3 3
1 1 1
2 2 3
3 3 2


Output


14


Input


4 10 2
2 3 8
3 4 7


Output


262

Note

In the first example, there are 3 houses, the maximum height of a house is 3, and there are 3 restrictions. The first restriction says the tallest house between 1 and 1 must be at most 1. The second restriction says the tallest house between 2 and 2 must be at most 3. The third restriction says the tallest house between 3 and 3 must be at most 2.

In this case, it is optimal to build houses with heights [1, 3, 2]. This fits within all the restrictions. The total profit in this case is 1^2 + 3^2 + 2^2 = 14.

In the second example, there are 4 houses, the maximum height of a house is 10, and there are 2 restrictions. The first restriction says the tallest house from 2 to 3 must be at most 8. The second restriction says the tallest house from 3 to 4 must be at most 7.

In this case, it's optimal to build houses with heights [10, 8, 7, 7]. We get a profit of 10^2+8^2+7^2+7^2 = 262. Note that there are two restrictions on house 3 and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house 1, we must still limit its height to be at most 10 (h=10).

Solution (in JAVA):

Solution:
//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();
        }
    }
}