CF1146G Zoning Restrictions

你计划在一条街道上建造住宅。街道上有 $n$ 个可用位置，这些位置从左到右编号为 $1$ 到 $n$。在每个位置，你可以建造一个高度为 $0$ 到 $h$ 的整数高度的房屋。 在每个位置，如果房屋高度为 $a$，你可以获得 $a^2$ 美元的收益。 然而，城市有 $m$ 条规划限制。第 $i$ 条限制规定，如果从第 $l_i$ 到第 $r_i$ 号位置中的最高房屋高度严格大于 $x_i$，你必须支付 $c_i$ 美元的罚款。 你希望通过建造房屋使利润最大化（总收益减去罚款）。请你计算可以获得的最大利润。

第一行包含三个整数 $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 5000$）。

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

在第一个样例中，最优方案是建造高度为 $[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$。 由 ChatGPT 4.1 翻译