Zoning Restrictions

题意翻译

你准备在一条街上建房子。这条街上共有$n$个地方可以用来建房子,每个房子高度最高为$h$。 若你建了一个高度为$a$的房子，那你将得到$a^2$的收益。 但是这条街有$m$个分区限制。 具体来说，对于第$i$个分区限制，若你在$l_i$到$r_i$这段区间内最高的房子的高度**严格大于**了$x_i$,那你将受到$c_i$的罚款。 求你的最大收益（房子收益$-$罚款）

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #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

说明

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