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.math.BigInteger;
import java.text.SimpleDateFormat;
import java.time.LocalDate;
import java.time.Period;
import static java.time.temporal.TemporalQueries.localDate;
import java.util.*;
import java.math.RoundingMode;

/*                               I   S   H   M   A   M
                                   R   U   H   A   N
 */
public class Main {

    private static String[] GetStringArray(ArrayList<String> ar) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    //Fastest I/O Class Start
    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

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

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {

                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception e) {

            }
            return str;
        }

    }
    //Fastest I/O Class End

    //Fastest Backup I/O Class Start
    static class CustomScanner {

        private final InputStream ins;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        CustomScanner() {
            this(System.in);
        }

        CustomScanner(InputStream in) {
            ins = in;
        }

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = ins.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) {
                return buffer[ptr++];
            } else {
                return -1;
            }
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
                ptr++;
            }
            return hasNextByte();
        }

        public String next() {
            return nextBuilder().toString();
        }

        public StringBuilder nextBuilder() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb;
        }

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

        public long nextLong() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || Integer.MAX_VALUE < nl) {
                throw new NumberFormatException();
            }
            return (int) nl;
        }

        public String[] nextA(int n) {
            String[] a = new String[n];
            nextA(a, n);
            return a;
        }

        public void nextA(String[] a, int n) {
            nextA(a, 0, n);
        }

        public void nextA(String[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = next();
            }
        }

        public int[] nextAInt(int n) {
            int[] a = new int[n];
            nextAInt(a, n);
            return a;
        }

        public void nextAInt(int[] a, int n) {
            nextAInt(a, 0, n);
        }

        public void nextAInt(int[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextInt();
            }
        }

        public long[] nextALong(int n) {
            long[] a = new long[n];
            nextALong(a, n);
            return a;
        }

        public void nextALong(long[] a, int n) {
            nextALong(a, 0, n);
        }

        public void nextALong(long[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextLong();
            }
        }

        public double[] nextADouble(int n) {
            double[] a = new double[n];
            nextADouble(a, n);
            return a;
        }

        public void nextADouble(double[] a, int n) {
            nextADouble(a, 0, n);
        }

        public void nextADouble(double[] a, int off, int len) {
            for (int i = off; i < off + len; i++) {
                a[i] = nextDouble();
            }
        }

        public List<Integer> nextLInt(int n) {
            List<Integer> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(in.nextInt());
            }
            return l;
        }

        public List<Long> nextLLong(int n) {
            List<Long> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(in.nextLong());
            }
            return l;
        }

        public List<Double> nextLDouble(int n) {
            List<Double> l = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                l.add(in.nextDouble());
            }
            return l;
        }
    }

    //Fastest Backup I/O Class End
    //Super Fast I/O class Start
    static class Reader {

        BufferedReader br;
        StringTokenizer st;
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {

                }
            }
            return st.nextToken();
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    break;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg) {
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) {
                return -ret;
            }
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg) {
                c = read();
            }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) {
                return -ret;
            }
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg) {
                c = read();
            }

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg) {
                return -ret;
            }
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) {
                buffer[0] = -1;
            }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) {
                fillBuffer();
            }
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) {
                return;
            }
            din.close();
        }
    }

    //Super Fast I/O Class End
    //public int sum = 0;
    //static int maxN = 10000007;
    //static long[] dp = new long[maxN];
    //static TreeMap<Integer, Integer> map = new TreeMap<>();
    static InputStream inputStream = System.in;
    static CustomScanner in = new CustomScanner(inputStream);
    static PrintWriter out = new PrintWriter(System.out);

    static class Clock {

        protected long start, stop;

        public void start() {
            start = System.currentTimeMillis();
        }

        public void stop() {
            stop = System.currentTimeMillis();
        }

        public String getTime() {
            return ((stop - start) + " ms");
        }
    }

    int gcd(int a, int b) {
        if (a == 0) {
            return Math.abs(b);
        }
        if (b == 0) {
            return Math.abs(a);
        }
        a = Math.abs(a);
        b = Math.abs(b);
        int az = Integer.numberOfTrailingZeros(a), bz = Integer.numberOfTrailingZeros(b);
        a >>>= az;
        b >>>= bz;
        while (a != b) {
            if (a > b) {
                a -= b;
                a >>>= Integer.numberOfTrailingZeros(a);
            } else {
                b -= a;
                b >>>= Integer.numberOfTrailingZeros(b);
            }
        }
        return (a << Math.min(az, bz));
    }

    long gcd(long a, long b) {
        if (a == 0) {
            return Math.abs(b);
        }
        if (b == 0) {
            return Math.abs(a);
        }
        a = Math.abs(a);
        b = Math.abs(b);
        int az = Long.numberOfTrailingZeros(a), bz = Long.numberOfTrailingZeros(b);
        a >>>= az;
        b >>>= bz;
        while (a != b) {
            if (a > b) {
                a -= b;
                a >>>= Long.numberOfTrailingZeros(a);
            } else {
                b -= a;
                b >>>= Long.numberOfTrailingZeros(b);
            }
        }
        return (a << Math.min(az, bz));
    }

    //get power in O(sqrt-n) complexity
    public long pow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 0) {
            return pow(a * a, b / 2);
        } else {
            return a * pow(a, b - 1);
        }
    }

    boolean isPrimeInt(int n) {
        if (n == 1 || n == 0) {
            return false;
        }

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

    boolean isPrimeLong(long n) {
        if (n == 1 || n == 0) {
            return false;
        }

        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

    Integer[] seivePrimes = new Integer[31];

    void eratosthenesSeive() {
        Integer maxN = 30;

        //seivePrimes[0] = seivePrimes[1] = 0;
        for (int i = 2; i * i <= maxN; i++) {
            if (seivePrimes[i] == null) {
                for (int j = i * i; j <= maxN; j += i) {
                    seivePrimes[j] = 0;
                }
            }
        }
    }

    //get sub sequence
    public static ArrayList<String> getAllSubSequence(String str) {
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }

        char ch = str.charAt(0);

        String subStr = str.substring(1);

        ArrayList<String> subSequences = getAllSubSequence(subStr);

        ArrayList<String> res = new ArrayList<>();
        for (String val : subSequences) {
            res.add(val);
            res.add(ch + val);
        }

        res.remove("");

        return res;
    }

    public static void main(String[] args) throws IOException {
        //FastReader in2 = new FastReader();
        Clock clock = new Clock();
        Solver solver = new Solver();

        clock.start();

        solver.solve();
        //out.close();
        clock.stop();
        //System.out.println(clock.getTime());
    }

    static void normalSieve(int n) {
        boolean prime[] = new boolean[n / 2];  //5

        Arrays.fill(prime, false); //F F F F T

        System.out.println("Primary Array");
        for (boolean b : prime) {
            System.out.print(b + " ");
        }
        System.out.println("");
        System.out.println("");

        for (int i = 3; i * i < n; i += 2) {
            System.out.println("i loop work. Here i= " + i);
            if (prime[i / 2] == false) { //---
                System.out.println("prime[i/2]==false executed here i/2= " + (i / 2));
                for (int j = i * i; j < n; j += i * 2) {
                    System.out.println("J loop work. Here j= " + j + " and (j/2)= " + (j / 2));
                    prime[j / 2] = true;
                }
            }

            System.out.println("\nArray after working i= " + i);
            for (boolean b : prime) {
                System.out.print(b + " ");
            }
            System.out.println("");
            System.out.println("");
            System.out.println("");
        }

        System.out.println("--OUTPUT SECTION----\n");

        //System.out.print("2(By default)  ");
        for (int i = 3; i < n; i += 2) {
            System.out.println("i= " + i + " working");
            System.out.println("i/2 index no: " + (i / 2) + " value: " + prime[i / 2]);
            if (prime[i / 2] == false) {
                System.out.println(i + " ");
            }
        }
        System.out.println("");
    }

    //bitwise sieve
    static int ifnotPrime(int prime[], int x) {
        // checking whether the value of element
        // is set or not. Using prime[x/64], 
        // we find the slot in prime array. 
        // To find the bit number, we divide x
        // by 2 and take its mod with 32.
        return (prime[x / 64] & (1 << ((x >> 1) & 31)));
    }

    // Marks x composite in prime[]
    static void makeComposite(int prime[], int x) {
        // Set a bit corresponding to given element.
        // Using prime[x/64], we find the slot 
        // in prime array. To find the bit number,
        // we divide x by 2 and take its mod with 32.
        prime[x / 64] |= (1 << ((x >> 1) & 31));
    }

    // Prints all prime numbers smaller than n.
    static void bitWiseSieve(int n) {
        // Assuming that n takes 32 bits, 
        // we reduce size to n/64 from n/2.
        int prime[] = new int[n / 64 + 1];

        // 2 is the only even prime so we
        // can ignore that loop starts from
        // 3 as we have used in sieve of
        // Eratosthenes .
        for (int i = 3; i * i <= n; i += 2) {

            // If i is prime, mark all its 
            // multiples as composite
            if (ifnotPrime(prime, i) == 0) {
                for (int j = i * i, k = i << 1;
                        j < n; j += k) {
                    makeComposite(prime, j);
                }
            }
        }

        // writing 2 separately
        System.out.printf("2 ");

        // Printing other primes
        /* for (int i = 3; i <= n; i += 2) {
            if (ifnotPrime(prime, i) == 0) {
                System.out.printf("%d ", i);
            }
        }
        System.out.println("");*/
    }
    //end

    static class Solver {

        public void solve() {

            int n = in.nextInt();
            int h = in.nextInt();
            int m = in.nextInt();
            
            int[] arr=new int[n];
            Arrays.fill(arr, h);
            
            while(m-- !=0){
                int l=in.nextInt();
                int r=in.nextInt();
                int x=in.nextInt();
                l--;r--;
                for (int i = l; i <=r; i++) {
                    if(x<arr[i])arr[i]=x;
                }
            }
            long sum=0;
            for (int i = 0; i < arr.length; i++) {
                sum+=(arr[i]*arr[i]);
            }
            out.println(sum);
            out.flush();
            
        }
    }
}