Zoning Restrictions Again

题意翻译

## 题目描述 你现在打算在一条街上面建个房子。 在这条街上有$n$个点可以让你建房子。这些点从左到右分别是$1$到$n$。 在每个点上,你可以建一个高为$0$到$h$(**整数**)的房子。 如果这个点的高度是$a$,那么你就要获利$a^2$美元。 这个城市有$m$个限制,第$i$个限制里从$l_i$到$r_i$(包含$l_i$和$r_i$)中最高的房子的高度不得超过$x_i$。 你希望建造的房子利润**最大**,输出最大利润。 ## 输入输出描述 ### 输入格式: 第一行有三个整数$n$, $h$, $m$ (1 $\leq$ $n$, $h$, $m$ $\leq$ 50) ——点的数量,最大高度,限制数量。 接下来$m$行包含三个整数$l_i$, $r_i$, $x_i$ (1 $\leq$ $l_i$ $\leq$ $r_i$ $\leq$ $n$, $0$ $\leq$ $x_i$ $\leq$ $h$)——第$i$限制左边界和右边界,在范围里的房子的最大高度 ### 输出格式: 输出一个整数——你能获得的最大利润 ## 说明 ##### 第一个数据: 有$3$栋房子,房子的最大高度是$3$,还有$3$个限制。 第一个限制是说从$1$到$1$的最高的房子的高度最多为$1$。 第二个限制是说从$2$到$2$的最高的房子的高度最多为$3$。 第三个限制是说从$3$到$3$的最高的房子的高度最多为$2$。 在这种情况下,建造高度较高的房屋是最佳选择是`[1, 2, 3]`。这符合所有限制。这种情况下的总利润是$1^2+3^2+2^2=14$ ##### 第二个数据 有$4$栋房子,房子的最大高度是$10$,还有$2$个限制。 第一个限制是说从$2$到$3$的最高的房子的高度最多为$8$。 第二个限制是说从$3$到$4$的最高的房子的高度最多为$7$。 在这种情况下,建造高度较高的房屋是最佳选择是`[10, 8, 7, 7]`。这符合所有限制。这种情况下的总利润是$10^2+8^2+7^2+7^2=262$。 **注意:第$3$个房子有两个限制,必须满足这两个限制;第$1$个房子没有任何限制,但是我们仍然要将高度限制设为$10$ ($h=10$)。**

题目描述

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 will gain $ a^2 $ dollars from it. The city has $ m $ zoning restrictions. The $ i $ -th restriction says that the tallest house from spots $ l_i $ to $ r_i $ (inclusive) must be at most $ x_i $ . You would like to build houses to maximize your profit. Determine the maximum profit possible.

输入输出格式

输入格式


The first line contains three integers $ n $ , $ h $ , and $ m $ ( $ 1 \leq n,h,m \leq 50 $ ) — the number of spots, the maximum height, and the number of restrictions. Each of the next $ m $ lines contains three integers $ l_i $ , $ r_i $ , and $ x_i $ ( $ 1 \leq l_i \leq r_i \leq n $ , $ 0 \leq x_i \leq h $ ) — left and right limits (inclusive) of the $ i $ -th restriction and the maximum possible height in that range.

输出格式


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

输入输出样例

输入样例 #1

3 3 3
1 1 1
2 2 3
3 3 2

输出样例 #1

14

输入样例 #2

4 10 2
2 3 8
3 4 7

输出样例 #2

262

说明

In the first example, there are $ 3 $ houses, the maximum height of a house is $ 3 $ , and there are $ 3 $ restrictions. The first restriction says the tallest house between $ 1 $ and $ 1 $ must be at most $ 1 $ . The second restriction says the tallest house between $ 2 $ and $ 2 $ must be at most $ 3 $ . The third restriction says the tallest house between $ 3 $ and $ 3 $ must be at most $ 2 $ . In this case, it is optimal to build houses with heights $ [1, 3, 2] $ . This fits within all the restrictions. The total profit in this case is $ 1^2 + 3^2 + 2^2 = 14 $ . In the second example, there are $ 4 $ houses, the maximum height of a house is $ 10 $ , and there are $ 2 $ restrictions. The first restriction says the tallest house from $ 2 $ to $ 3 $ must be at most $ 8 $ . The second restriction says the tallest house from $ 3 $ to $ 4 $ must be at most $ 7 $ . In this case, it's optimal to build houses with heights $ [10, 8, 7, 7] $ . We get a profit of $ 10^2+8^2+7^2+7^2 = 262 $ . Note that there are two restrictions on house $ 3 $ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $ 1 $ , we must still limit its height to be at most $ 10 $ ( $ h=10 $ ).