Zoning Restrictions Again

Description:

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.

Sample Input:

3 3 3
1 1 1
2 2 3
3 3 2

Sample Output:

14

Sample Input:

4 10 2
2 3 8
3 4 7

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