더운 날들

문제

일본이 겨울인 이 시기에, 남반구에 있는 오스트레일리아에서는 더운 날이 계속되고 있다. 오스트레일리아에 사는 IOI 군은, 어떤 D 일간의 일기 예보를 바탕으로 입을 옷의 계획을 세우기로 했다. i 일째 (1 ≦ i ≦ D) 의 최고 기온은 $T_{i}$ 도라고 예보되어 있다.

IOI 군은 N 종류의 옷을 가지고 있으며, 그 옷들에는 1 부터 N 까지의 번호가 붙어 있다. 옷 j (1 ≦ j ≦ N) 는 최고 기온이 $A_{j}$ 도 이상 $B_{j}$ 도 이하인 날에 입기에 적합하다. 또한, 각각의 옷에는 「화려함」이라고 불리는 정수가 정해져 있으며, 옷 j 의 화려함은 $C_{j}$ 이다.

D 일간의 각각의 날에 대해, IOI 군은 최고 기온이 일기 예보를 따를 때 입기에 적합한 옷 중 하나를 입을 옷으로 고른다. 같은 옷을 몇 번 골라도 되고, D 일간 한 번도 선택되지 않는 옷이 있어도 된다.

비슷한 옷을 연속해서 입는 것을 되도록 피하려고 생각한 IOI 군은, 연속하는 날에 입는 옷의 화려함의 차의 절댓값의 합을 가능한 한 크게 하려고 생각했다. 즉, i 일째에 옷 $x_{i}$ 를 골랐다고 할 때, 값 |$C_{x_{1}}$ - $C_{x_{2}}$| + |$C_{x_{2}}$ - $C_{x_{3}}$| + … + |$C_{x_{D-1}}$ - $C_{x_{D}}$| 을 최대로 하고 싶다. 이 최댓값을 구하는 프로그램을 작성하시오.

입력

입력은 1 + D + N 개의 줄로 이루어진다.

첫째 줄에는 2 개의 정수 D, N (2 ≦ D ≦ 200,1 ≦ N ≦ 200) 이 공백으로 구분되어 주어진다. D 는 옷의 계획을 세우는 날수, N 은 IOI 군이 가지고 있는 옷의 종류의 수를 나타낸다.

이어지는 D 개의 줄 중 i 번째 줄 (1 ≦ i ≦ D) 에는 1 개의 정수 $T_{i}$ (0 ≦ $T_{i}$ ≦ 60) 이 주어진다. 이는 i 일째의 최고 기온이 $T_{i}$ 도라고 예보되어 있음을 나타낸다.

이어지는 N 개의 줄 중 j 번째 줄 (1 ≦ j ≦ N) 에는 3 개의 정수 $A_{j}$, $B_{j}$, $C_{j}$ (0 ≦ $A_{j}$ ≦ $B_{j}$ ≦ 60,0 ≦ $C_{j}$ ≦ 100) 이 주어진다. 이는 옷 j 가 최고 기온이 $A_{j}$ 도 이상 $B_{j}$ 도 이하인 날에 입기에 적합하며, 화려함이 $C_{j}$ 임을 나타낸다.

최고 기온이 일기 예보를 따를 때 입기에 적합한 옷이, D 일간의 어느 날에 대해서도 1 개 이상 존재함이 보장된다.

출력

연속하는 날에 입는 옷의 화려함의 차의 절댓값의 합, 즉, 값 |$C_{x_{1}}$ - $C_{x_{2}}$| + |$C_{x_{2}}$ - $C_{x_{3}}$| + … + |$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 에서, 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

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

예제 출력 2

300

예제 2 에서, 1 일째에는 옷 2 를, 2 일째에는 옷 2 를, 3 일째에는 옷 1 을, 4 일째에는 옷 2 를, 5 일째에는 옷 1 을 골라야 한다. 이때, 구하는 값은 |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 이 된다.