题目描述

你现在打算在一条街上面建个房子。 在这条街上有$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$)。

样例

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

14

4 10 2
2 3 8
3 4 7

262