#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 *C _{i}* 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

*S*and

_{i}*E*, and will gain

_{i}*H*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.

_{i}## 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, *S _{i}*,

*E*and

_{i}*H*.

_{i}## Output

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

## Limits

For all subtasks: 0 ≤ S_{i}, E_{i} < N, 0 ≤ H_{i}, C_{i} ≤ 10^{9}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 22 | 1.5s | 256MB | Minimum |

2 | 12 | 42 | 1.5s | 256MB | Minimum |

3 | 30 | 22 | 1.5s | 256MB | Minimum |

4 | 22 | 62 | 1.5s | 256MB | Minimum |

5 | 26 | 102 | 1.5s | 256MB | Minimum |

6 | 0 | 2 | 1.5s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o collectmushrooms4 -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512