Problem Description

The Kazuma Kingdom has $ N $ towns, each with one hero.

The hero of the $ i $ $(1\ \leq\ i\ \leq\ N)$ -th town can defeat up to $ A_i $ monsters in total.

The heroes want experience points, so they will defeat as many monsters as possible that come to their town.

You are the Demon King and have control over $ M $ bases.

From the $ j $ $(1\ \leq\ j\ \leq\ M)$ -th base, you can freely dispatch a total of $ B_j $ monsters to towns $L_j,\ L_j+1,\ ...,\ R_j$.

As a result, the number of monsters not defeated by the heroes will inflict damage on the Kazuma Kingdom.

Find the maximum total damage that can be inflicted on the Kazuma Kingdom.

Input Format

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

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ M $ $ L_1 $ $ R_1 $ $ B_1 $ $ L_2 $ $ R_2 $ $ B_2 $ $\vdots$ $ L_M $ $ R_M $ $ B_M $

Output Format

Output the maximum total damage that can be inflicted on the Kazuma Kingdom.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

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

Sample Output #2

4

Sample Input #3

10
9 7 4 11 5 100 95 3 55 12
12
2 3 6
1 2 2
1 4 8
3 5 5
3 5 6
4 4 6
5 7 3
5 8 5
1 10 52
9 10 13
7 9 2
8 9 5

Sample Output #3

83

Sample Input #4

1
1
10
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

Sample Output #4

9999999999

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ N\ \leq\ 3000$
• $1\ \leq\ M\ \leq\ 3000$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $1\ \leq\ B_j\ \leq\ 10^9$
• $1\ \leq\ L_j\ \leq\ R_j\ \leq\ N$

Sample Explanation 1

By dispatching as follows, you can inflict a total of $ 7 $ damage on the Kazuma Kingdom:
- From the 1st base, dispatch $ 5 $ monsters to the 2nd town and $ 2 $ monsters to the 3rd town.
- From the 2nd base, dispatch $ 4 $ monsters to the 2nd town.
- From the 3rd base, dispatch $ 3 $ monsters to the 3rd town.

Sample Explanation 4

Be careful of overflow.

见题面 Input 部分

见题面 Output 部分