CF1162A.Zoning Restrictions Again

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.

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.

Print a single integer, the maximum profit you can make.

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$ ).