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