VOL - Volunteers

no tags 

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 Ai 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 Si-th day to Ti-th day, we will pay them $Ci. 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 Ai. M lines follow, each contains three integers Si, Ti and Ci. 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]


Added by:Fudan University Problem Setters
Date:2008-07-30
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Chinese National Olympiad in Informatics 2008, Day 1