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

public class ZoningRestrictions {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int H = scanner.nextInt();
        int M = scanner.nextInt();
        MaxFlowSolver solver = new Dinic();
        Node src = solver.addNode();
        Node snk = solver.addNode();
//        long tot = 0;
        ArrayList<Restriction>[] restrictions = new ArrayList[N];
        Restriction[] store = new Restriction[M];
        for(int i = 0; i < N; i++) restrictions[i] = new ArrayList<>();
        Node[] restNodes = new Node[M];
        for(int i = 0; i < M; i++) {
            store[i] = new Restriction(scanner.nextInt()-1, scanner.nextInt()-1, scanner.nextInt(), scanner.nextInt(), i);
            for(int j = store[i].l; j <= store[i].r; j++) {
                restrictions[j].add(store[i]);
            }
            restNodes[i] = solver.addNode();
            solver.link(restNodes[i], snk, store[i].c);
        }
        Node[][] spotNodes = new Node[N][H+1];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j <= H; j++) {
                spotNodes[i][j] = solver.addNode();
                if (j > 0) {
                    solver.link(spotNodes[i][j-1], spotNodes[i][j], H*H- (j)*(j));
                    solver.link(spotNodes[i][j], spotNodes[i][j-1], Integer.MAX_VALUE);
                }
                else {
                    solver.link(src, spotNodes[i][j], H*H);
                }
//                tot += j*j;
            }
            int min = H;
            for(Restriction r: restrictions[i]) {
                min = Math.min(r.x, min);
                for(int h = r.x; h <= H; h++) {
                    solver.link(spotNodes[i][h], restNodes[r.n], Integer.MAX_VALUE);
                }
            }
//            out.println(min);
//            for(int j = 0; j < min; j++) {
//                solver.link(spotNodes[i][min], snk, 0);
//            }
            
        }
        long mf = solver.getMaxFlow(src, snk);
//        out.println(mf);
        out.println(H*H*N - mf);
        out.flush();
    }
    
    public static class Restriction {
        int l, r, x, c, n;
        public Restriction(int ll, int rr, int xx, int cc, int nn) {
            l  =ll; r = rr; x = xx; c = cc; n = nn;
        }
    }
    
    public static class Node {
        private Node() {}
        List<Edge> edges = new ArrayList<>();
        int index;
        int dist;
        int currentarc;
    }
    public static class Edge {
        boolean forward;
        Node from, to;
        long flow;
        final long capacity;
        Edge dual;
        long cost;
        protected Edge(Node s, Node d, long c, boolean f) {
            forward = f;
            from = s;
            to = d;
            capacity = c;
        }
        void addFlow(long amt) {
            flow += amt;
            dual.flow -= amt;
        }
        long remaining() {return capacity- flow;}
    }
    public static abstract class MaxFlowSolver {
        List<Node> nodes = new ArrayList<>();
    
        public void link(Node n1, Node n2, long capacity) {
            link(n1, n2, capacity, 0);
        }
    
        public void link(Node n1, Node n2, long capacity, long cost) {
            Edge e12 = new Edge(n1, n2, capacity, true);
            Edge e21 = new Edge(n2, n1, 0, false);
            e12.dual = e21;
            e21.dual = e12;
            n1.edges.add(e12);
            n2.edges.add(e21);
            e12.cost = cost;
            e21.cost = -cost;
        }
    
        void link(int n1, int n2, long capacity) {
            link(nodes.get(n1), nodes.get(n2), capacity);
        }
    
        protected MaxFlowSolver(int n) {
            for (int i = 0; i < n; i++) {
                addNode();
            }
        }
    
        protected MaxFlowSolver() {
            this(0);
        }
    
        public abstract long getMaxFlow(Node src, Node snk);
        
        public Node addNode() {
            Node node = new Node();
            node.index = nodes.size();
            nodes.add(node);
            return node;
        }
    }
    public static class Dinic extends MaxFlowSolver {
        long BlockingFlow(Node src, Node snk) {
            int N = nodes.size();
            for(Node u: nodes) {
                u.dist = -1;
                u.currentarc = 0;
            }
            Node[] Q = new Node[N];
            src.dist = 0;
            int head= 0, tail = 0;
            Q[tail++] = src;
            while(head < tail) {
                Node x = Q[head++];
                List<Edge> succ = x.edges;
                for(Edge edge: succ) {
                    if (edge.to.dist == -1 && edge.remaining() > 0) {
                        edge.to.dist = edge.from.dist + 1;
                        Q[tail++]  =edge.to;
                    }
                }
            }
            if (snk.dist == -1) return 0;
            long flow, totflow = 0;
            do {
                flow = dfs(src, snk, Long.MAX_VALUE);
                totflow += flow;
            } while(flow > 0);
            return totflow;
        }
        long dfs(Node v, Node snk, long mincap) {
            if (v == snk) return mincap;
            for(; v.currentarc < v.edges.size(); v.currentarc++) {
                Edge edge = v.edges.get(v.currentarc);
                if (edge.from.dist + 1 == edge.to.dist && edge.remaining() > 0) {
                    long flow = dfs(edge.to, snk, Math.min(mincap, edge.remaining()));
                    if (flow > 0) {
                        edge.addFlow(flow);
                        return flow;
                    }
                }
            }
            return 0;
        }
        public long getMaxFlow(Node src, Node snk) {
            long flow, totflow = 0;
            while((flow = BlockingFlow(src, snk)) != 0) {
                totflow += flow;
            }
            return totflow;
        }
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}