CF1146G.Zoning Restrictions

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 can gain $a^2$ dollars from it.

The city has $m$ zoning restrictions though. The $i$-th restriction says that if the tallest house from spots $l_i$ to $r_i$ is strictly more than $x_i$, you must pay a fine of $c_i$.

You would like to build houses to maximize your profit (sum of dollars gained minus fines). Determine the maximum profit possible.

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

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

然而，该城市有 $m$ 条分区限制规定。第 $i$ 条限制规定：若位置 $l_i$ 到 $r_i$（含端点）范围内最高房屋的高度严格大于 $x_i$，则你必须缴纳 $c_i$ 美元罚款。

你希望建造房屋以使总利润（总收益减去总罚款）最大化。请确定可能获得的最大利润。

The first line contains three integers $n,h,m$ ($1 \leq n,h,m \leq 50$) — the number of spots, the maximum height, and the number of restrictions, respectively.

Each of the next $m$ lines contains four integers $l_i, r_i, x_i, c_i$ ($1 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq h$, $1 \leq c_i \leq 5\,000$).

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

接下来的 $m$ 行中，每行包含四个整数 $l_i, r_i, x_i, c_i$（$1 \leq l_i \leq r_i \leq n$，$0 \leq x_i \leq h$，$1 \leq c_i \leq 5\,000$）。

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

输出一个整数，表示你能获得的最大利润。

In the first example, it's optimal to build houses with heights $[1, 3, 2]$. We get a gain of $1^2+3^2+2^2 = 14$. We don't violate any restrictions, so there are no fees, so the total profit is $14 - 0 = 14$.

In the second example, it's optimal to build houses with heights $[10, 8, 8, 10]$. We get a gain of $10^2+8^2+8^2+10^2 = 328$, and we violate the second restriction for a fee of $39$, thus the total profit is $328-39 = 289$. Note that even though there isn't a restriction on building $1$, we must still limit its height to be at most $10$.

在第一个例子中，最优方案是建造高度为 $[1, 3, 2]$ 的房屋。我们获得的收益为 $1^2+3^2+2^2 = 14$。我们未违反任何限制条件，因此无需支付任何费用，总利润为 $14 - 0 = 14$。

在第二个例子中，最优方案是建造高度为 $[10, 8, 8, 10]$ 的房屋。我们获得的收益为 $10^2+8^2+8^2+10^2 = 328$，且违反了第二条限制条件，需缴纳 $39$ 的费用，因此总利润为 $328-39 = 289$。注意：尽管对第 $1$ 栋房屋没有明确的限制条件，我们仍必须将其高度限制为不超过 $10$。