Problem Statement

On an infinitely long number line, there are $N$ lakes and $M$ fish.

The range of the $i$-th lake is represented by $[L_i - 0.5, L_i + 0.5)$. The $i$-th fish is initially located at coordinate $F_i$.

When a fish is at coordinate $x$, if there exists a lake whose range contains coordinate $x$, the fish is said to be in the water; otherwise, the fish is said to be on land.

Each fish has a strength: the $i$-th fish has strength $B_i$ when on land and strength $W_i$ when in the water. It is guaranteed that $B_i \leq W_i$ holds for all $i$.

You may perform the following operations any number of times.

• Choose one fish and move it by $1$ in the positive direction of the number line. This operation costs $1$.
• Choose one fish and move it by $1$ in the negative direction of the number line. This operation costs $1$.

Let $S$ be the total strength of the $M$ fish after the operations, and let $C$ be the total cost incurred by the operations. Find the maximum value of $S-C$.

Constraints

• All inputs are integers.
• $1 \leq N, M \leq 10^5$
• $0 \leq L_1 < L_2 < \dots < L_N \leq 10^9$
• $0 \leq F_i \leq 10^9$
• $0 \leq B_i \leq W_i \leq 10^9$

Input

The input is given from standard input in the following format.

$N$ $M$
$L_1$ $L_2$ $\cdots$ $L_N$
$F_1$ $B_1$ $W_1$
$F_2$ $B_2$ $W_2$
$\vdots$
$F_M$ $B_M$ $W_M$

Output

Output the answer.

Sample

4 3
8 11 14 2023
7 10 12
14 14 14
2013 8 12

33

1 1
0
0 0 1000000000

1000000000

6 5
57 59 60 72 85 91
12 3 55
16 58 96
94 77 85
97 20 77
37 7 53

254