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

public class Main implements Runnable{
    public static void main(String[] args){
        //new Thread(null,new Main(),"Thread-1",1024*1024*10).start();
        new Main().run();
    }
    int n,h,m;
    private void solve() throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        n=in.nextInt();h=in.nextInt();m=in.nextInt();
        Dinic dinic=new Dinic(5001,m*n*n*m*2);
        int last=5000;
        for(int i=1;i<=n;i++){
            dinic.addEdge(0,trans(i,0),100000,0);
            for(int j=1;j<=h;j++){
                dinic.addEdge(trans(i,j-1),trans(i,j),h*h-(j-1)*(j-1),0);
            }
        }
        int id=trans(n,h)+1;
        for(int t=0;t<m;t++){
            int l=in.nextInt(),r=in.nextInt(),x=in.nextInt(),c=in.nextInt();
            if(x>=h)continue;
            for(int i=l;i<=r;i++){
                dinic.addEdge(trans(i,x+1),id,100000,0);
            }
            dinic.addEdge(id,last,c,0);
            id++;
        }
        out.println(n*h*h-dinic.maxFlow(0,last));
        out.flush();
    }
    int trans(int a,int b){
        return (a-1)*(h+1)+b+1;
    }
    class Dinic {
        private int[] it;
        private int[] dp;//深度
        private int[] head, to, cap, next;//边的各个参数
        int cnt;

        public Dinic(int PointNum, int EdgeNum) {
            it = new int[PointNum];
            dp = new int[PointNum];
            head = new int[PointNum];
            to = new int[EdgeNum];
            cap = new int[EdgeNum];
            next = new int[EdgeNum];
            init();
        }

        public void init() {
            int cnt=0;
            Arrays.fill(head, -1);
        }

        public void addEdge(int a, int b, int capacity, int revcap) {
            cap[cnt] = capacity;    cap[cnt | 1] = revcap;
            to[cnt] = b;            to[cnt | 1] = a;
            next[cnt] = head[a];    next[cnt | 1] = head[b];
            head[a] = cnt;          head[b] = cnt | 1;
            cnt += 2;
        }

        public int maxFlow(int s, int t) {
            int sum = 0, flow;
            while (bfs(s, t)) {//求分层图
                for (int i = 0; i < head.length; i++)
                    it[i] = head[i];
                flow = dfs(s, t, Integer.MAX_VALUE);//dfs求出流量
                if (flow != 0) sum += flow;//若流量不为0，加入
                else break;//流量为0，说明没有增广路，返回最大流
            }
            return sum;
        }

        private boolean bfs(int s, int t) {
            Arrays.fill(dp, 0);
            dp[s] = 1;
            Queue<Integer> qu = new LinkedList<>();
            qu.add(s);
            while (!qu.isEmpty()) {
                int cur = qu.poll();
                for (int i = head[cur]; i != -1; i = next[i])
                    if (dp[to[i]] == 0 && cap[i] > 0) {
                        dp[to[i]] = dp[cur] + 1;
                        qu.add(to[i]);
                    }
            }
            return dp[t] != 0;
        }

        private int dfs(int cur, int t, int flow) {
            if (cur == t) return flow;
            int sum = 0, f;
            for (int i = it[cur]; i != -1; it[cur] = i = next[i]) {//当前弧优化
                if (cap[i] > 0 && dp[cur] + 1 == dp[to[i]]) {//若满足边权不为0且满足分层图的性质
                    f = dfs(to[i], t, Math.min(flow, cap[i]));//继续找增广路
                    if (f == 0) dp[to[i]] = 0;//去掉已经增广完的点
                    sum += f;//统计最大流
                    flow -= f;//剩余容量
                    cap[i] -= f;
                    cap[i ^ 1] += f;//更新剩余容量
                    if (flow == 0) return sum;//若前面已经流完了，直接返回
                }
            }
            return sum;//返回最大流量
        }
    }

    @Override
    public void run() {
        try {
            solve();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    void shuffle(int[]a,int l,int r){
        Random rnd=new Random();
        for (int i=r; i>l+1; i--) {
            int j=rnd.nextInt(i),tmp=a[j];
            a[j]=a[i-1];
            a[i-1]=tmp;
        }
    }
    class InputReader{
        StreamTokenizer tokenizer;
        public InputReader(InputStream stream){
            tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
            tokenizer.ordinaryChars(33,126);
            tokenizer.wordChars(33,126);
        }
        public String next() throws IOException {
            tokenizer.nextToken();
            return tokenizer.sval;
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public boolean hasNext() throws IOException {
            int res=tokenizer.nextToken();
            tokenizer.pushBack();
            return res!=tokenizer.TT_EOF;
        }
    }
}