Fashionista

Sang-geun is planning what to wear on each of the next $D$ days (day $1$ through day $D$). Because clothing style is closely tied to the day's high temperature, he plans based on the weather forecast. The high temperature on day $i$ is $T_i$.

Sang-geun owns $N$ pieces of clothing, numbered from $1$ to $N$. Clothing $j$ ($1 \le j \le N$) can only be worn on a day whose high temperature is between $A_j$ and $B_j$ inclusive, and its flashiness is $C_j$.

He may wear the same clothing on several days, and some clothing may never be worn.

Wearing similar clothing on consecutive days is unappealing, so he wants to maximize the total difference in flashiness between the clothing worn on adjacent days. That is, if he wears clothing $x_i$ on day $i$, he wants to maximize $|C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}|$.

Write a program that computes the maximum value of this sum.

The first line contains $D$ and $N$. ($2 \le D, N \le 200$)

Each of the next $D$ lines contains the high temperature of one day; the $i$-th line contains $T_i$. ($0 \le T_i \le 60$)

Each of the following $N$ lines describes one piece of clothing with $A_j$, $B_j$, $C_j$. ($0 \le A_j \le B_j \le 60$, $0 \le C_j \le 100$)

On every day there is at least one piece of clothing that can be worn.

Print the maximum total difference in flashiness on a single line.

In the first example, wearing clothing $4$ on day $1$, clothing $2$ on day $2$, and clothing $3$ on day $3$ gives $|40 - 90| + |90 - 60| = 80$, which is the maximum.