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 自动生成**

### Sample Explanation 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 $ となり，これが最大値である． - - - - - - ### Sample Explanation 2 入出力例 $ 2 $ において，$ 1 $ 日目には服 $ 2 $ を，$ 2 $ 日目には服 $ 2 $ を，$ 3 $ 日目には服 $ 1 $ を，$ 4 $ 日目には服 $ 2 $ を，$ 5 $ 日目には服 $ 1 $ を選ばなければならない．このとき，求める値は $ |100\ -\ 100|\ +\ |100\ -\ 0|\ +\ |0\ -\ 100|\ +\ |100\ -\ 0|\ =\ 300 $ となる．