After the successful bid for the Olympics, Bubu, through tireless efforts, finally became the head of the human resources department at a company under the Olympic Organizing Committee. Shortly after taking office, Bubu encountered a difficult problem: recruiting a group of short-term volunteers for a new Olympic project that was about to launch. After estimation, it was determined that the project would take $N$ days to complete, with at least $A_i$ people needed on day $i$.

Bubu learned that there are $M$ types of volunteers available for recruitment. The $i$-th type can work from day $S_i$ to day $T_i$, and the recruitment cost is $C_i$ per person. As a new official eager to make a good impression, Bubu wants to recruit enough volunteers with the minimum possible cost, but this is not his specialty! Therefore, Bubu has come to you, hoping you can help him design an optimal recruitment plan.

Input

The first line contains two integers $N$ and $M$, representing the number of days to complete the project and the number of types of volunteers available.

The next line contains $N$ non-negative integers, representing the minimum number of volunteers needed each day.

The next $M$ lines each contain three integers $S_i, T_i, C_i$, with the meanings as described above. For convenience, we can assume that the number of volunteers of each type is infinite.

Output

A single integer representing the total cost of the optimal plan you designed.

Examples

Input 1

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

Output 1

14

Note

Recruit 3 volunteers of the first type and 4 volunteers of the third type.

Constraints

• For 30% of the data, $1 \le N, M \le 10$, $1 \le A_i \le 10$.
• For 100% of the data, $1 \le N \le 1000$, $1 \le M \le 10000$. All other data involved in the problem does not exceed $2^{31}-1$.