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 \leq n,h,m \leq 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 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq 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$).

Difficulty: interview

Starter code:

Solutions:
n, h, m = map(int, input().split())
a = [h] * n
for i in range(m):
    l, r, x = map(int, input().split())
    for i in range(l - 1, r):
        a[i] = min(a[i], x)
s = 0
for i in range(n):
    s += a[i] ** 2
print(s)

n, h, m = map(int, input().split())
a = [h] * n
for _ in range(m):
	l, r, c = map(int, input().split())
	for i in range(l - 1, r):
		a[i] = min(a[i], c)
print(sum(k ** 2 for k in a))

n, h, m = list(map(int, input().split()))
a = [h] * (n + 1)
for i in range(m):
	l, r, x = list(map(int, input().split()))
	for j in range(l, r + 1):
		a[j] = min(a[j], x)
ans = 0
for i in range(1, n + 1):
	ans += a[i] * a[i]
print(ans)


n,h,m=map(int,input().split())
k = [h]*(n+1)
for _ in range(m):
	l,r,x=map(int,input().split())
	for i in range(l,r+1):
		k[i]=min(k[i],x)
t=0
for i in range(1,n+1):
	t += k[i]**2
print(t)

n, h, m = map(int, input().split())
houses = [h for i in range(n)]
for i in range(m):
    l, r, x = map(int, input().split())
    for i in range(l - 1, r):
        houses[i] = min(x, houses[i])
ans = 0
for house in houses:
    ans += house ** 2
print(ans)

N, H, M = map(int, input().split())
st = [H]*(N+1)
for _ in range(M):
    l, r, x = map(int, input().split())
    for i in range(l, r+1):
        st[i] = min(st[i], x)
print(sum(a**2 for a in st[1:])) 

# -*- coding: utf-8 -*-
# @Time    : 2019/5/5 1:05
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : A. Zoning Restrictions Again.py


def main():
    n, h, m = list(map(int, input().split()))
    spots = [h] * n
    for _ in range(m):
        l, r, x = list(map(int, input().split()))
        for i in range(l - 1, r):
            spots[i] = min(spots[i], x)
    ret = sum([a ** 2 for a in spots])
    print(ret)


def __starting_point():
    main()

__starting_point()

n, h, m = list(map(int, input().split()))
ans = [h] * n
for i in range(m):
    l, r, x = list(map(int, input().split()))
    for j in range(l - 1, r):
        ans[j] = min(ans[j], x)

cnt = 0
for i in range(n):
    cnt += ans[i] * ans[i]
print(cnt)

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)
    n, h, m = read_int_array()
    restr = [h]*n
    for _ in range(m):
        l, r, x = read_int_array()
        for i in range(l-1, r):
            restr[i] = min(restr[i], x)
    write(sum(x*x for x in restr))


main()


#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('C:/Users/njhab/Desktop/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    n,h,m= map(int, sys.stdin.readline().split(' '))
    a=[]
    for i in range(n):
        a.append(h)
    for i in range(m):
        l,r,x=map(int, sys.stdin.readline().split(' '))
        for j in range(l-1,r):
            a[j]=min(a[j],x)
    ans=0
    for aa in a:
        ans+=aa*aa
    print(ans)

    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

n, h, m = map(int, input().split())

A = [h] * n

for i in range(m):
    l, r, mh = map(int, input().split())
    for i in range(l-1, r):
        A[i] = min(A[i], mh)
        
ans = 0

for i in A:
    ans += i**2

print(ans)

import sys
input = sys.stdin.readline

n,h,m=map(int,input().split())

arr=[]
for i in range(n):
	arr.append(h)

for i in range(m):
	l,r,x=map(int,input().split())
	for j in range(l-1,r):
		arr[j]=min(arr[j],x)

count=0
for i in range(n):
	count+=arr[i]**2

print(count)

n,h,m=list(map(int,input().strip().split()))
buil=[h]*n
for i in range(m):
    l,r,x=list(map(int,input().strip().split()))
    for j in range(l-1,r):
        buil[j]=min(buil[j],x)
op=0
for i in buil:
    op+=i*i
print(op)

n, h, m = [int(i) for i in input().split()]
a = [h] * (n + 1)
for i in range(m):
    l, r, x = [int(i) for i in input().split()]
    for j in range(l, r + 1):
        a[j] = min(a[j], x)
ans = 0
for i in range(1, n + 1):
    ans += a[i] * a[i]
print(ans)


n,h,m=[int(x) for x in input().split()]
counter=0
a=[h]*n
for i in range(m):
    l,r,x=[int(x) for x in input().split()]
    for i in range(l-1,r):
        a[i]=min(a[i],x,h)
for item in a:
    counter+=item**2
print(counter)


n, h, m = list(map(int,input().split()))
maksi = [h] * n
tab = [[] for i in range(m)]
for i in range(m):
	tab[i] = list(map(int,input().split()))
for i in range(m):
	l = tab[i][0]
	r = tab[i][1]
	for j in range(l - 1, r):
		maksi[j] = min(maksi[j], tab[i][2])
wyn = 0
for i in range(n):
	wyn += maksi[i]**2
print(wyn)

#	!/usr/bin/env python3
#	encoding: UTF-8
#	Modified: <04/May/2019 10:39:45 PM>


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology (IIIT),Gwalior


# ///==========Libraries, Constants and Functions=============///


import sys


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return list(map(int, sys.stdin.readline().split()))


def input(): return sys.stdin.readline().strip()


# ///==========MAIN=============///

inf = float('inf')


def main():
    n, h, m = get_ints()
    arr = [inf] * n
    for tc in range(m):
        l, r, x = get_ints()
        l -= 1
        r -= 1
        for i in range(l, r + 1):
            arr[i] = min(arr[i], x)
    ans = 0
    for i in arr:
        if i == inf:
            ans += (h**2)
        else:
            ans += (i**2)
    print(ans)


def __starting_point():
    main()

__starting_point()

def getn():
    return int(input())
def getns():
    return [int(x)for x in input().split()]
# n=getn()
# ns=getns()
n,h,m=getns()
hs=[h]*(n+1)
for i in range(m):
    l,r,x=getns()
    for i in range(l,r+1):
        hs[i]=min(hs[i],x)
ans=0
for i in range(1,n+1):
    ans+=hs[i]*hs[i]
print(ans)

n, h, m = list(map(int, input().split()))
dp = [h for _ in range(n)]
for _ in range(m):
	l, r, x = list(map(int, input().split()))
	for i in range(l - 1, r):
		dp[i] = min(dp[i], x)
ans = 0
for x in dp:
	ans += x * x
print(ans)



def go():
    n, h, m = list(map(int, input().split(' ')))
    houses = [h] * n
    for _ in range(m):
        l, r, x = [int(w) for w in input().split(' ')]
        l -= 1
        r -= 1
        for i in range(l, r + 1):
            houses[i] = min(houses[i], x)
    answer = 0
    for i in range(n):
        answer += houses[i] ** 2

    return answer

print(go())


def main():
    n, h, m = list(map(int, input().split()))

    restrictions = [h for _ in range(n)]
    for i in range(m):
        l, r, x = list(map(int, input().split()))
        for j in range(l, r+1):
            restrictions[j-1] = min(restrictions[j-1], x)

    res = 0
    for x in range(n):
        res += restrictions[x]**2

    print(res)


def __starting_point():
    main()

__starting_point()

ints=[int(x) for x in input().split()]
n=ints[0]
h=ints[1]
m=ints[2]
maxheights=[h for i in range(n)]
for i in range(m):
    integers=[int(x) for x in input().split()]
    for j in range(integers[0]-1,integers[1]):
        maxheights[j]=min(maxheights[j],integers[2])
maxSum=0
for i in range(n):
    maxSum=maxSum+(maxheights[i])**2
print(maxSum)

n, h, m = [int(x) for x in input().split(' ')]

dollars = 0
houses = [h] * n
for i in range(m):
    l, r, x = [int(x) for x in input().split(' ')]
    for j in range(l, r+1):
        houses[j-1] = min(x, houses[j-1])

print(sum([a*a for a in houses]))


n, h, m = [int(item) for item in input().split()]

x = [h ** 2 for _ in range(n)]
for _ in range(m):
    l, r, xi = [int(item) for item in input().split()]
    for u in range(l - 1, r):
        x[u] = min(xi ** 2, x[u])

print(sum(x))