问题

在日本是冬季的这个时候，澳大利亚位于南半球的地区一直很热。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要从适合天气预报下穿的衣服中选择一件来穿。可以多次选择同一件衣服，也可以有几件衣服在这 $D$ 天里一次也没选到。

IOI想尽量避免连续穿相似的衣服，所以他决定使相邻天的衣服花哨度之差的绝对值总和尽可能大。换句话说，假设在第 $i$ 天穿衣服 $x_i$，IOI想要最大化值 $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$。请编写一个程序来求解最大值。

输入

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

第一行有两个整数 $D$ 和 $N$ ($2 \leq D \leq 200$，$1 \leq N \leq 200$)，用空格分隔。$D$ 是制订衣服计划的天数，$N$ 是IOI拥有的不同衣服的数量。

接下来的 $D$ 行中，第 $i$ 行 ($1 \leq i \leq D$) 有一个整数 $T_i$ ($0 \leq T_i \leq 60$)，表示预测第 $i$ 天的最高温度为 $T_i$ 度。

接下来的 $N$ 行中，第 $j$ 行 ($1 \leq j \leq 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$。

保证在天气预报下，每一天都存在一件适合的衣服。

输出

输出连续天穿的衣服花哨度之差的绝对值总和，即值 $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$ 的最大值，输出在一行中。

示例 1

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

输出示例 1

80

对于示例 $1$，第一天可选的衣服有衣服 $3$ 和衣服 $4$，第二天可选的衣服有衣服 $2$ 和衣服 $3$，第三天只能选衣服 $3$。选择在第一天穿衣服 $4$，第二天穿衣服 $2$，第三天穿衣服 $3$。那么第一天和第二天衣服的花哨度之差的绝对值为 $|40 - 90| = 50$，第二天和第三天衣服的花哨度之差的绝对值为 $|90 - 60| = 30$。总和为 $80$，这是最大值。

示例 2

5 2
26
28
32
29
34
30 35 0
25 30 100

输出示例 2

300

对于示例 $2$，第一天要选择衣服 $2$，第二天要选择衣服 $2$，第三天要选择衣服 $1$，第四天要选择衣服 $2$，第五天要选择衣服 $1$。那么结果为 $|100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300$。