Problem Description

Usa Railway is a railway for rabbits. Usa Railway has one long track running east-west and $N$ stations. The stations are numbered from $1$ to $N$ from west to east. Each station has a capacity, and station $i$ ( $1 \leq i \leq N$ ) can accommodate at most $C_i$ rabbits at the same time.

Usa Railway plans to operate $M$ trains. Train $i$ ( $1 \leq i \leq M$ ) departs from station $A_i$ at time $S_i$ and arrives at station $A_i+1$ at time $T_i$, and can carry up to $B_i$ rabbits. Since Usa Railway has only one track, the departure and arrival times of the trains are scheduled to avoid overtaking. Also, there are no pairs of trains departing from the same station at the same time, or arriving at the same station at the same time. However, it is possible for a train to depart from a station at the same time another train arrives at the same station. In this case, regardless of the station's capacity, rabbits can freely board or disembark until the train departs.

Currently, there are $C_1$ rabbits at station $1$, and all of them want to go to station $N$. By cleverly transporting the rabbits without exceeding the capacity of each station, what is the maximum number of rabbits that can be transported to station $N$?

Input Format

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

$ N $ $ M $ $ C_1 $ $ C_2 $ $ ... $ $ C_N $ $ S_1 $ $ T_1 $ $ A_1 $ $ B_1 $ $ S_2 $ $ T_2 $ $ A_2 $ $ B_2 $ $ : $ $ S_M $ $ T_M $ $ A_M $ $ B_M $

Output Format

Output the maximum number of rabbits that can be transported to station $N$.

Sample Input and Output

Sample Input #1

3 4
9 2 9
1 2 1 3
2 3 2 4
6 9 2 5
2 4 1 5

Sample Output #1

5

Sample Input #2

3 2
1 9 9
1 2 1 5
3 4 2 5

Sample Output #2

1

Sample Input #3

2 1
1000000000 2016
999999999 1000000000 1 1000000000

Sample Output #3

2016

Sample Input #4

2 0
12 24

Sample Output #4

0

Sample Input #5

4 11
8 2 3 9
1 2 1 1
2 4 1 1
4 5 1 6
6 7 1 1
6 7 2 3
5 6 2 5
3 4 2 3
4 6 3 2
6 7 3 1
7 8 3 4
8 9 3 2

Sample Output #5

7

Notes/Hints

Constraints

• $2 \leq N \leq 500,000$.
• $0 \leq M \leq 500,000$.
• $1 \leq C_i, B_i \leq 10^9$.
• $1 \leq S_i < T_i \leq 10^9$.
• $1 \leq A_i \leq N-1$.
• There does not exist $i, j (i \neq j)$ such that $A_i = A_j$ and $S_i \leq S_j$ and $T_i \geq T_j$.
• This means that overtaking does not occur, and there are no pairs of trains departing from the same station at the same time, or arriving at the same station at the same time.

Sample Explanation 1

The following plan can transport 5 rabbits:
- 3 rabbits board train 1.
- All board train 2 at station 2.
- All disembark at station 3.
- 2 rabbits board train 4.
- All disembark at station 2 and wait for train 3.
- All board train 3.
- All disembark at station 3.

见题面 Input 部分

见题面 Output 部分