← 返回题目列表

Codeforces · 1146/G

G. 分区限制

中文机器翻译题面 查看原题

您计划在街道上建造住房。街道上有 $$$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 5\,000$$$)。

输出

打印一个整数,表示您可以获得的最大利润。

示例

输入 #1

3 3 3
1 1 1 1000
2 2 3 1000
3 3 2 1000

输出 #1

14

输入 #2

4 10 2
2 3 8 76
3 4 7 39

输出 #2

289

注意

在第一个示例中,最佳建造高度为 $$$[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$$$。