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