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.

你计划在一条街道上建造住宅。街道上有 $n$ 个可供建房的位置，从左到右依次编号为 $1$ 到 $n$。在每个位置上，你可以建造一栋高度为 $0$ 到 $h$（含）之间的整数的房屋。

在每个位置上，若所建房屋高度为 $a$，则你能获得 $a^2$ 美元的收益。

城市共有 $m$ 条分区限制。第 $i$ 条限制规定：从位置 $l_i$ 到 $r_i$（含端点）的所有房屋中，最高房屋的高度至多为 $x_i$。

你希望以最大化总收益的方式建造房屋。请确定可能获得的最大收益。

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.

第一行包含三个整数 $n$、$h$ 和 $m$（$1 \leq n,h,m \leq 50$）——分别为点位数量、最大高度以及限制条件的数量。

接下来的 $m$ 行中，每行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 \leq l_i \leq r_i \leq n$，$0 \leq x_i \leq h$）——分别表示第 $i$ 个限制条件的左边界、右边界（均含端点）以及该区间内允许的最大高度。

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

在第一个例子中，共有 $3$ 座房屋，每座房屋的最大高度为 $3$，且存在 $3$ 条限制。第一条限制要求区间 $[1, 1]$ 内最高房屋的高度至多为 $1$；第二条限制要求区间 $[2, 2]$ 内最高房屋的高度至多为 $3$；第三条限制要求区间 $[3, 3]$ 内最高房屋的高度至多为 $2$。

此时，最优方案是建造高度为 $[1, 3, 2]$ 的房屋，该方案满足所有限制条件。此时总利润为 $1^2 + 3^2 + 2^2 = 14$。

在第二个例子中，共有 $4$ 座房屋，每座房屋的最大高度为 $10$，且存在 $2$ 条限制。第一条限制要求区间 $[2, 3]$ 内最高房屋的高度至多为 $8$；第二条限制要求区间 $[3, 4]$ 内最高房屋的高度至多为 $7$。

此时，最优方案是建造高度为 $[10, 8, 7, 7]$ 的房屋，所得利润为 $10^2+8^2+7^2+7^2 = 262$。注意：房屋 $3$ 同时受到两条限制约束，二者均须满足。此外，尽管房屋 $1$ 没有显式的限制条件，其高度仍不得超过最大允许值 $10$（即 $h=10$）。