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-separated 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]