ACM ICPC World Finals 2009, sponsored by IBM and hosted by KTH, Royal Institute of Technology will be held in Stockholm, Sweden. This contest will last for N(1<= N <= 1000) days. We need at least A_i volunteers in the i-th day. Now there are M(1<= M <=10000) kind of volunteers. The i-th type of volunteers will work from S_i-th day to T_i-th day, we will pay them $C_i. Now your task is to minimize the money KTH pay for all the volunteers.

Input

Ten test cases(given one after another, you have to process all!). For each test case:

The first line contains two space-seperated integers N and M. The second line contains N nonnegative integers A_i. M lines follow, each contains three integers S_i, T_i and C_i. You may assume you can hire almost unlimited number of every type of volunteers.

Tip: During your calculation, int in C/C++/Java or longint in Pascal is enough.

Output

For each test case:

Output one line with an integer - the minimum cost.

Example

Input:
3 3
2 3 4
1 2 2
2 3 5
3 3 2
[and 9 test cases more]
Output:
14
[and 9 test cases more]