Problem Background

WuuTue owns a circus, which tours the country, and recently arrived in City T.

Problem Description

City T has a dedicated performance street, a straight street running east-west, with $n$ stages numbered $1, 2, \dots, n$ from west to east.

WuuTue plans to hold $M$ performances on the performance street, where the $i$-th performance will occupy the consecutive stages from $l_i$ to $r_i$ (including $l_i$ and $r_i$), and WuuTue knows that the $i$-th performance will earn $v_i$ yuan.

Since the stages on the performance street are designed for human performances, they need to be reinforced for animal performances, with the $i$-th stage requiring $c_i$ yuan for reinforcement, and this cost is incurred only once and can be reused. That is, if multiple performances use stage $i$, only one reinforcement cost is needed.

Of course, if WuuTue finds that a performance may not be profitable due to high reinforcement costs, he may cancel the performance.

Since WuuTue is not very skilled, please help him calculate the maximum income he can earn in yuan.

Input Format

The first line contains two space-separated integers $n$ and $m$, representing the number of stages and performances, respectively.

The second to the $n+1$-th lines each contain one integer, where the $i+1$-th line's integer represents the cost $c_i$ to reinforce the $i$-th stage.

The $n+2$-th to the $n+m+1$-th lines each contain three space-separated integers, where the $n+i+1$-th line's three integers $l_i$, $r_i$, and $v_i$ represent that the $i$-th performance needs to occupy the consecutive stages from $l_i$ to $r_i$ and can earn $v_i$ yuan.

Output Format

One line: an integer representing the maximum income WuuTue can earn.

Sample Input and Output

Input Sample #1

7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5

Output Sample #1

4

Input Sample #2

2 1
0
3
1 2 5

Output Sample #2

2

Input Sample #3

3 1
10
10
10
1 3 10

Output Sample #3

0

Notes

This problem uses bundled testing

For $20\%$ of the data, $1 \le n, m \le 100$.

Another $20\%$ of the data, $v_i = c_i = 1$.

Another $20\%$ of the data, $l_i = r_i$.

For $100\%$ of the data, $1 \le n, m \le 10^6, 0 \le v_i, c_i \le 10^9, 1 \le l_i \le r_i \le n$.

见题面 Input 部分

见题面 Output 部分