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.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //This code is not meant for understanding, proceed with caution
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int n = ni(), h = ni(), m = ni();
        int[][] res = new int[m][3];
        for(int i = 0; i< m; i++)res[i] = new int[]{ni()-1, ni()-1, ni()};
        MyTreeSet<Integer> set = new MyTreeSet<>();
        Arrays.sort(res, (int[] i1, int[] i2) -> Integer.compare(i1[0], i2[0]));
        PriorityQueue<Pair> q = new PriorityQueue<>();
        set.add(h);
        int ans = 0;
        for(int i = 0, j = 0; i< n; i++){
            while(j< m && res[j][0]<=i){
                set.add(res[j][2]);
                q.add(new Pair(res[j][1], res[j][2]));
                j++;
            }
            while(!q.isEmpty() && q.peek().ri<i)set.remove(q.poll().x);
            ans+=set.first()*set.first();
        }
        pn(ans);
    }
    class Pair implements Comparable<Pair>{
        int ri;int x;
        public Pair(int r, int X){
            ri=r;x=X;
        }
        public int compareTo(Pair p){
            return Integer.compare(ri, p.ri);
        }
    }
    class MyTreeSet<T>{
        private int size;
        private TreeMap<T, Integer> map;
        public MyTreeSet(){
            size = 0;
            map = new TreeMap<>();
        }
        public int size(){return size;}
        public int dsize(){return map.size();}
        public boolean isEmpty(){return size==0;}
        public void add(T t){
            size++;
            map.put(t, map.getOrDefault(t, 0)+1);
        }
        public boolean remove(T t){
            if(!map.containsKey(t))return false;
            size--;
            int c = map.get(t);
            if(c==1)map.remove(t);
            else map.put(t, c-1);
            return true;
        }
        public int freq(T t){return map.getOrDefault(t, 0);}
        public boolean contains(T t){return map.getOrDefault(t,0)>0;}
        public T ceiling(T t){return map.ceilingKey(t);}
        public T floor(T t){return map.floorKey(t);}
        public T first(){return map.firstKey();}
        public T last(){return map.lastKey();}
    }
    
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1e9+7, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)2e5+1;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}