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.math.*;
public class mmm
{
    static class InputReader {
        public BufferedReader br;
        public StringTokenizer token;
        public InputReader(InputStream stream)
        {
            br=new BufferedReader(new InputStreamReader(stream),32768);
            token=null;
        }

        public String next()
        {
            while(token==null || !token.hasMoreTokens())
            {
                try
                {
                    token=new StringTokenizer(br.readLine());
                }
                catch(IOException e)
                {
                    throw new RuntimeException(e);
                }
            }
            return token.nextToken();
        }

        public int nextInt()
        {
            return Integer.parseInt(next());
        }

        public long nextLong()
        {
            return Long.parseLong(next());
        }
    }
    /*static class card{
    long up;
    int down;
    public card(long u,int d)
    {
    this.up=u;
    this.down=d;
    }
    }
    static class sort implements Comparator<card>
    {
    public int compare(card o1,card o2)
    {
    if(o1.up!=o2.up)
    return (int)(o1.up-o2.up);
    else
    return (int)(o1.down-o2.down);
    }
    }
    static void shuffle(long a[])
    {
    List<Long> l=new ArrayList<>();
    for(int i=0;i<a.length;i++)
    l.add(a[i]);
    Collections.shuffle(l);
    for(int i=0;i<a.length;i++)
    a[i]=l.get(i);
    }

    static long gcd(long a,long b)
    {
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
    }
    static int ans1=Integer.MAX_VALUE,ans2=Integer.MAX_VALUE,ans3=Integer.MAX_VALUE,ans4=Integer.MAX_VALUE;
    static boolean v[]=new boolean[101];
    static void dfs(Integer so,Set<Integer> s[]){
    if(!v[so.intValue()])
    {
    v[so]=true;
    for(Integer h:s[so.intValue()])
    {
    if(!v[h.intValue()])
    dfs(h,s);
    }
    }
    }
    static class Print{
    public PrintWriter out;
    Print(OutputStream o)
    {
    out=new PrintWriter(o);
    }
    }
    static int CeilIndex(int A[], int l, int r, int key) 
    { 
    while (r - l > 1) { 
    int m = l + (r - l) / 2; 
    if (A[m] >= key) 
    r = m; 
    else
    l = m; 
    } 

    return r; 
    } 

    static int LongestIncreasingSubsequenceLength(int A[], int size) 
    { 
    // Add boundary case, when array size is one 
    int[] tailTable = new int[size]; 
    int len; // always points empty slot 
    tailTable[0] = A[0]; 
    len = 1; 
    for (int i = 1; i < size; i++) { 
    if (A[i] < tailTable[0]) 
    // new smallest value 
    tailTable[0] = A[i]; 

    else if (A[i] > tailTable[len - 1]) 
    // A[i] wants to extend largest subsequence 
    tailTable[len++] = A[i]; 

    else
    // A[i] wants to be current end candidate of an existing 
    // subsequence. It will replace ceil value in tailTable 
    tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]; 
    } 
    return len; 
    }*/
    /*static int binary(int n)
    {
    int s=1;
    while(n>0)
    {
    s=s<<1;
    n--;
    }
    return s-1;
    }
    static StringBuilder bin(int i,int n)
    {
    StringBuilder s=new StringBuilder();
    while(i>0)
    {
    s.append(i%2);
    i=i/2;
    }
    while(s.length()!=n)
    {
    s.append(0);
    }
    return s.reverse();
    }*/
    public static void main(String args[])
    {
        InputReader sc=new InputReader(System.in);
        int n=sc.nextInt();
        int h=sc.nextInt();
        int m=sc.nextInt();
        int a[]=new int[n+1];
        int v[]=new int[n+1];
        for(int i=0;i<m;i++)
        {
            int l=sc.nextInt();
            int r=sc.nextInt();
            int x=sc.nextInt();
            for(int j=l;j<=r;j++)
            {
                if(v[j]==0)
                {
                    a[j]=x;
                    v[j]=1;
                }
                else
                {
                    a[j]=Math.min(a[j],x);
                    v[j]=1;
                }
            }
        }
        long sum=0;
        for(int i=1;i<=n;i++)
        {
           if(v[i]==0)
           sum=sum+(h*h);
           else
           sum=sum+(a[i]*a[i]); 
        }
        System.out.println(sum);
    }
}