AT_joi2013yo_d.暑い日々 (Hot days)

日本正值冬季，而澳大利亚，位于南半球，此时正经历炎热的天气。居住在澳大利亚的 IOI 君决定根据未来 $ D $ 天的天气预报来安排他的穿衣计划。预报显示，第 $ i $ 天（$ 1 \leq i \leq D $）的最高气温为 $ T_i $ 度。

IOI 君拥有 $ N $ 种不同的衣服，它们分别编号为 $ 1 $ 到 $ N $。编号为 $ j $ 的衣服（$ 1 \leq j \leq N $）适合最高气温在 $ A_j $ 到 $ B_j $ 度之间的日子穿着。此外，每件衣服都有一个表示“派手度”的整数，衣服 $ j $ 的派手度为 $ C_j $。

在这 $ D $ 天中，IOI 君每天会根据当天的最高气温选择一件适合的衣服来穿。他可以在多天内多次选择同一件衣服，也可以不选择某些衣服。为避免连续多天穿相似风格的衣服，IOI 君想要最大化每天所穿衣服的派手度之差的绝对值之和。具体来说，他要最大化 $ |C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \ldots + |C_{x_{D-1}} - C_{x_D}| $。请编写程序计算该最大值。

输入包含 $ 1 + D + N $ 行。

第一行有两个整数 $ D $ 和 $ N $（$ 2 \leq D \leq 200 $，$ 1 \leq N \leq 200 $），分别表示穿衣计划的天数和 IOI 君拥有的衣服种类数。

接下来的 $ D $ 行，每行一个整数 $ T_i $（$ 0 \leq T_i \leq 60 $），表示第 $ i $ 天的最高气温预报为 $ T_i $ 度。

接下来的 $ N $ 行，每行三个整数 $ A_j, B_j, C_j $（$ 0 \leq A_j \leq B_j \leq 60 $，$ 0 \leq C_j \leq 100 $），表示衣服 $ j $ 适合在最高气温为 $ A_j $ 度到 $ B_j $ 度的日子穿，且其派手度为 $ C_j $。

保证每一天至少有一件衣服适合穿。

输出一个整数，表示最大化的连续两天所穿衣服的派手度差的绝对值之和。

示例

示例说明 1

在示例 1 中，第 1 天可以选择的衣服是衣服 3 和衣服 4，第 2 天可以选择衣服 2 和衣服 3，第 3 天只能选择衣服 3。若在第 1 天选择衣服 4，第 2 天选择衣服 2，第 3 天选择衣服 3，即 $ x_1 = 4 $，$ x_2 = 2 $，$ x_3 = 3 $，那么第 1 天与第 2 天的派手度差的绝对值是 $ |40 - 90| = 50 $，第 2 天与第 3 天是 $ |90 - 60| = 30 $。总和为 $ 80 $，这是最大值。

示例说明 2

在示例 2 中，第 1 天必须选择衣服 2，第 2 天也要选择衣服 2，第 3 天选择衣服 1，第 4 天重新选择衣服 2，第 5 天选择衣服 1。此时，计算的总和为 $ |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 $。

本翻译由 AI 自动生成