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 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;
        }
    }
}