패셔니스타

상근이는 앞으로 $D$일 동안(1일부터 $D$일까지) 매일 어떤 옷을 입을지 계획하려고 한다. 옷 스타일은 그날의 최고 기온과 밀접한 관련이 있어서, 일기 예보를 바탕으로 계획을 세운다. $i$일의 최고 기온은 $T_i$이다.

상근이는 옷을 총 $N$벌 가지고 있으며, 각 옷에는 1번부터 $N$번까지 번호가 붙어 있다. 옷 $j$($1 \le j \le N$)는 최고 기온이 $A_j$ 이상 $B_j$ 이하인 날에만 입을 수 있고, 화려한 정도는 $C_j$이다.

같은 옷을 여러 날 입어도 되고, 한 번도 입지 않는 옷이 있어도 된다.

비슷한 옷을 연속으로 입으면 매력이 떨어지므로, 이웃한 날에 입은 옷의 화려함 차이의 합이 최대가 되도록 입으려고 한다. 즉, $i$일에 옷 $x_i$를 입었다면 $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$를 최대로 하려고 한다.

이 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 $D$와 $N$이 주어진다. ($2 \le D, N \le 200$)

다음 $D$개 줄에는 각 날의 최고 기온이 한 줄에 하나씩 주어지며, $i$번째 줄은 $T_i$이다. ($0 \le T_i \le 60$)

그다음 $N$개 줄에는 옷의 정보가 한 줄에 하나씩 $A_j$, $B_j$, $C_j$ 순으로 주어진다. ($0 \le A_j \le B_j \le 60$, $0 \le C_j \le 100$)

어떤 날이든 입을 수 있는 옷이 적어도 하나는 존재한다.

화려함 차이의 합의 최댓값을 한 줄에 출력한다.

첫 번째 예제에서 1일에 4번 옷, 2일에 2번 옷, 3일에 3번 옷을 입으면 $|40 - 90| + |90 - 60| = 80$이 되며, 이 값이 최댓값이다.