Problem Description

During this winter season in Japan, Australia, located in the Southern Hemisphere, is experiencing hot days. IOI, who lives in Australia, decided to plan his outfits based on a weather forecast for a certain period of $ D $ days. The forecast predicts that the highest temperature on the $ i $-th day ($1 \leq i \leq D$) will be $ T_i $ degrees.

IOI has $ N $ types of clothes, numbered from $ 1 $ to $ N $. Clothes $ j $ ($1 \leq j \leq N$) is suitable for days with a highest temperature between $ A_j $ degrees and $ B_j $ degrees inclusive. Each clothing also has an integer value called "flashiness," where the flashiness of clothes $ j $ is $ C_j $.

For each of the $ D $ days, IOI will choose one of the clothes suitable for the predicted highest temperature. The same clothes can be chosen multiple times, and some clothes may not be chosen at all during the $ D $ days.

IOI wants to avoid wearing similar clothes consecutively and aims to maximize the sum of the absolute differences in flashiness between consecutive days. That is, if he chooses clothes $ x_i $ for the $ i $-th day, he wants to maximize the value $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$. Write a program to find this maximum value.

Input Format

The input consists of $ 1 + D + N $ lines.

The first line contains two integers $ D, N $ ($2 \leq D \leq 200$, $1 \leq N \leq 200$), separated by a space. $ D $ represents the number of days for which the clothing plan is made, and $ N $ is the number of types of clothes IOI has.

The next $ D $ lines contain one integer each, $ T_i $ ($0 \leq T_i \leq 60$), which represents the predicted highest temperature on the $ i $-th day.

The next $ N $ lines contain three integers each, $ A_j, B_j, C_j $ ($0 \leq A_j \leq B_j \leq 60$, $0 \leq C_j \leq 100$), which indicate that clothes $ j $ is suitable for days with a highest temperature between $ A_j $ degrees and $ B_j $ degrees, and has a flashiness of $ C_j $.

It is guaranteed that for every day of the $ D $ days, there is at least one suitable clothes to wear according to the weather forecast.

Output Format

Output the maximum sum of the absolute differences in flashiness between consecutive days, i.e., the value $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$ in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

80

Sample Input #2

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

Sample Output #2

300

Notes/Hints

Sample Explanation 1

In Sample Input #1, the candidates for clothes on the 1st day are clothes 3 and 4, on the 2nd day are clothes 2 and 3, and on the 3rd day is only clothes 3. Choosing clothes 4 on the 1st day, clothes 2 on the 2nd day, and clothes 3 on the 3rd day, i.e., $ x_1 = 4 $, $ x_2 = 2 $, $ x_3 = 3 $, results in the absolute difference in flashiness between the 1st and 2nd day being $ |40 - 90| = 50 $ and between the 2nd and 3rd day being $ |90 - 60| = 30 $. The total is $ 80 $, which is the maximum value.

Sample Explanation 2

In Sample Input #2, clothes 2 must be chosen on the 1st and 2nd days, clothes 1 on the 3rd and 5th days, and clothes 2 on the 4th day. The value to be maximized is $ |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 $.

见题面 Input 部分

见题面 Output 部分