No submission language available for this problem.

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.

Samples

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

14

4 10 2
2 3 8
3 4 7

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