Problem Description

You have found $N$ treasure chests numbered from $1$ to $N$. Initially, all the chests are locked and cannot be opened. Unlocking chest $i$ will allow you to gain $a_i$ yen.

You have $M$ friends who are locksmiths, numbered from $1$ to $M$. If you pay locksmith $i$ $c_i$ yen to request unlocking, all locked chests numbered from $l_i$ to $r_i$ (inclusive) will be unlocked.

Your goal is to maximize $Y - X$, where $X$ is the total amount of money paid to the locksmiths and $Y$ is the total amount of money gained from the unlocked chests. Find the maximum possible value of $Y - X$.

Input Format

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

$N$ $M$ $a_1$ $a_2$ $\cdots$ $a_N$ $l_1$ $r_1$ $c_1$ $\vdots$ $l_M$ $r_M$ $c_M$

Output Format

Output the maximum possible value of $Y - X$, where $X$ is the total amount of money paid to the locksmiths and $Y$ is the total amount of money gained from the unlocked chests.

Sample Input and Output

Sample Input #1

4 3
20 10 100 10
1 3 100
2 4 50
1 1 50

Sample Output #1

70

Sample Input #2

2 2
10 10
1 1 1000
1 2 100

Sample Output #2

0

Sample Input #3

20 10
40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15
2 11 221
14 20 14
2 11 126
1 8 273
5 11 94
2 8 48
12 15 83
2 7 13
5 16 269
3 12 115

Sample Output #3

760

Notes/Hints

Constraints

• All given inputs are integers.
• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq a_i, c_i \leq 10^9$
• $1 \leq l_i \leq r_i \leq N$

Sample Explanation 1

• It is optimal to pay locksmith $2$ $50$ yen to unlock chests $2, 3, 4$ and gain $10 + 100 + 10 = 120$ yen. Note that you do not need to unlock all chests.

Sample Explanation 2

• It is possible that it is optimal not to request unlocking from any locksmith.

见题面 Input 部分

见题面 Output 部分