collectmushrooms4

Problem Description

Gug is collecting mushrooms again. This time he is collecting it in linear land, where there are N houses arranged in a row. Getting a permit to dig mushrooms in front of house i costs Ci dollars, but once it is bought, Gug can direct as many minions as he wants to dig mushrooms there. Gug has M minions. Minion i wants to pick mushrooms between houses Si and Ei, and will gain Hi dollars if it is allowed to do so. Help Gug decide a subset of minions to allow to pick mushrooms such that he gains the most amount of money.

Input

The first line of input will contain two integers, N and M.

The second line of input will contain N integers, representing the array C.

The next M lines of input will contain three integers each, Si, Ei and Hi.

Output

The output should contain one integer, the maximum net profit Gug can gain.

Limits

For all subtasks: 0 ≤ Si, Ei < N, 0 ≤ Hi, Ci ≤ 109.

Subtask 1 (10%): 1 ≤ N ≤ 500, 1 ≤ M ≤ 15.

Subtask 2 (12%): 1 ≤ N ≤ 2000, 1 ≤ M ≤ 20.

Subtask 3 (30%): 1 ≤ N ≤ 200, 1 ≤ M ≤ 200.

Subtask 4 (22%): 1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000.

Subtask 5 (26%): 1 ≤ N ≤ 300000, 1 ≤ M ≤ 300000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

2 1
0 3
0 1 5

Sample Output 1

2

Sample Input 2

7 4
3 2 3 2 1 2 3
0 1 5
1 2 5
2 4 3
6 6 5

Sample Output 2

4

Submitting to 'collectmushrooms4'


You're not logged in! Click here to login


Submitting to 'collectmushrooms4'


You're not logged in! Click here to login


Submitting .cpp to 'collectmushrooms4'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 17
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 10
2 12
3 30
4 22
5 26
6 0