Problem Name: Hot Days
Problem
Problem Description: In Japan, where it is currently winter, it has been hot in Australia, which is located in the southern hemisphere. IOI-kun, who lives in Australia, decided to plan his clothing based on a weather forecast for D days. On the i-th day (1 ≦ i ≦ D), the highest temperature is forecast to be Ti degrees.
IOI-kun has N types of clothing, each labeled with a number from 1 to N. Clothing j (1 ≦ j ≦ N) is suitable for wearing on days when the highest temperature is between Aj and Bj degrees. Each piece of clothing also has a "flashiness" value, represented by an integer Cj.
For each of the D days, IOI-kun will choose one item of clothing that is suitable for wearing according to the weather forecast. The same item of clothing may be chosen multiple times, and it is also possible for some items of clothing to not be chosen at all during the D days.
IOI-kun wants to avoid wearing similar clothing on consecutive days as much as possible, so he wants to maximize the sum of the absolute differences in flashiness between the clothing he wears on consecutive days. That is, if he chooses item x1 on day 1, item x2 on day 2, and so on up to item xD on day D, he wants to maximize the value |Cx1 - Cx2| + |Cx2 - Cx3| + ... + |CxD-1 - CxD|. Write a program to calculate this maximum value.
Input
The input consists of 1+D+N lines.
The first line contains two integers D and N (2 ≦ D ≦ 200, 1 ≦ N ≦ 200), separated by a space. D is the number of days for which clothing must be planned, and N is the number of types of clothing that IOI-kun has.
The i-th line of the following D lines (1 ≦ i ≦ D) contains one integer Ti (0 ≦ Ti ≦ 60), which represents the highest temperature forecast for the i-th day.
Each of the following N lines (1 ≦ j ≦ N) contains three integers Aj, Bj, and Cj (0 ≦ Aj ≦ Bj ≦ 60, 0 ≦ Cj ≦ 100), which indicate that clothing j is suitable for wearing on days when the highest temperature is between Aj and Bj degrees, and has a flashiness value of Cj.
It is guaranteed that there is at least one item of clothing that is suitable for wearing on any day according to the weather forecast for the D days.
Output
Output a single integer, the maximum value of |Cx1 - Cx2| + |Cx2 - Cx3| + ... + |CxD-1 - CxD| over all possible choices of clothing for the D days.
Examples
Example 1
Input:
3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

Output:
80

Explanation:
On the first day, the candidate clothing items are clothing 3 and 4. On the second day, the candidate clothing items are clothing 2 and 3. On the third day, the candidate clothing item is clothing 3 only. Choosing clothing 4 on the first day, clothing 2 on the second day, and clothing 3 on the third day maximizes the sum of the absolute differences in flashiness between consecutive days. Specifically, the absolute difference in flashiness between clothing on the first and second days is |40 - 90| = 50, and the absolute difference in flashiness between clothing on the second and third days is |90 - 60| = 30. The sum of these differences is 80, which is the maximum value possible.
Example 2
Input:
5 2
26
28
32
29
34
30 35 0
25 30 100

Output:
300

Explanation:
On the first day, IOI-kun must choose clothing 2. On the second day, he must choose clothing 2 again. On the third day, he must choose clothing 1. On the fourth day, he must choose clothing 2 again. On the fifth day, he must choose clothing 1. The maximum value of the sum of the absolute differences in flashiness between consecutive days is |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300.