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 org.omg.PortableInterceptor.INACTIVE;

import java.io.*;
import java.math.*;
import java.util.*;

@SuppressWarnings("Duplicates")
// author @mdazmat9
public class codeforces{
 static long abs=1000000007;
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int test = 1;
        for (int ind = 0; ind < test; ind++) {
            int n=sc.nextInt();
            int h=sc.nextInt();
            int m=sc.nextInt();
            HashMap<Integer,Integer> map=new HashMap<>();
            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(!map.containsKey(j)){
                        map.put(j,x);
                    }
                    else {
                        int num=map.get(j);
                        if(num>x){
                            map.put(j,x);
                        }
                    }
                }
            }
            long ans=0;
            for(int i=1;i<=n;i++){
                if(map.containsKey(i)){
                    int num=map.get(i);
                    ans+=(num*num);
                }
                else {
                    ans+=(h*h);
                }
            }
            out.println(ans);

        }
        out.flush();
    }


    static class The_Comparator implements Comparator<Integer> {
        public int compare(Integer str1, Integer str2)
        {
            return str2-str1;
        }
    }


    static    class nodes{
        ArrayList<Integer> list=new ArrayList<>();
        int k;
    }


    static class Node {
        int index;
        boolean removable;
        List<Node> children = new ArrayList<>();
        Node parent;

        Node(int index) {
            this.index = index;
        }

        boolean isGood() {
            if (parent == null || !removable) {
                return false;
            }
            for (Node c : children) {
                if (!c.removable) {
                    return false;
                }
            }
            return true;
        }

    }


    public static double logb( double a, double b )
    {
        return Math.log(a) / Math.log(b);
    }

    static long fast_pow(long a, long b) {
        if(b == 0)
            return 1L;

        long val = fast_pow(a, b / 2);

        if(b % 2 == 0)
            return val * val % mod;
        else
            return val * val % mod * a % mod;
    }
    static long mod = (long)1e9 + 7;
    static   void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    static long gcd(long a , long b)
    {
        if(b == 0)
            return a;
        return gcd(b , a % b);
    }

}
class Scanner {
    public BufferedReader reader;
    public StringTokenizer st;

    public Scanner(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        st = null;
    }

    public String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = reader.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            } catch (Exception e) {
                throw (new RuntimeException());
            }
        }
        return st.nextToken();
    }

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

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

class OutputWriter {
    BufferedWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException {
        writer.write(i);
    }

    public void print(String s) throws IOException {
        writer.write(s);
    }

    public void print(char[] c) throws IOException {
        writer.write(c);
    }

    public void close() throws IOException {
        writer.close();
    }

}
class Pair {
    long x;
    long y;

    // Constructor
    public Pair(long x, long y)
    {
        this.x = x;
        this.y = y;
    }
}
class Compare {

    static void compare(Pair arr[], int n)
    {
        // Comparator to sort the pair according to second element
        Arrays.sort(arr, new Comparator<Pair>() {
            @Override public int compare(Pair p1, Pair p2)
            {
                return (int)((p2.x - p2.y)-(p1.x-p1.y));
            }
        });
    }
}

class Graph {

    int V;
    ArrayList<Integer>[] adjListArray;

    // constructor
    Graph(int V) {
        this.V = V;

        adjListArray = new ArrayList[V];

        for (int i = 0; i < V; i++) {
            adjListArray[i] = new ArrayList<>();
        }
    }

    // Adds an edge to an undirected graph
    void addEdge(int src, int dest) {

        adjListArray[src].add(dest);
        adjListArray[dest].add(src);
    }


    ArrayList<Integer> DFSUtil(int u, boolean visited[], int parent,ArrayList<Integer> list)
    {
        // Mark the current node as visited
        visited[u] = true;

        for (int i = 0; i < adjListArray[u].size(); i++) {
            int n = adjListArray[u].get(i);
            list.add(n);

            if (!visited[i]) {
                DFSUtil(n, visited, u,list);
            }
        }
        return list;

    }


    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS(int r,int c) {
        // Mark all the vertices as not visited(set as
        // false by default in java)
        boolean visited[] = new boolean[V];
        ArrayList<Integer> list=new ArrayList<>();
        // Call the recursive helper function to print DFS traversal
        boolean bool=true;

    }


}