Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3745
Salary Increasing

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Edward has established a company with n staffs. He is such a kind man that he did Q times salary increasing for his staffs. Each salary increasing was described by three integers (l, r, c). That means Edward will add c units money for the staff whose salaxy is in range [l, r] now. Edward wants to know the amount of total money he should pay to staffs after Q times salary increasing.

Input

The input file contains multiple test cases.

Each case begin with two integers : n -- which indicate the amount of staff; Q -- which indicate Q times salary increasing. The following n integers each describes the initial salary of a staff(mark as ai). After that, there are Q triples of integers (li, ri, ci) (i=1..Q) which describe the salary increasing in chronological.

1 ≤ n ≤ 105 , 1 ≤ Q ≤ 105 , 1 ≤ ai ≤ 105 , 1 ≤ liri ≤ 105 , 1 ≤ ci ≤ 105 , ri < li+1

Process to the End Of File.

Output

Output the total salary in a line for each case.

Sample Input

4 1
1 2 3 4
2 3 4

Sample Output

18

Hint

{1, 2, 3, 4} → {1, 4, 6, 7}.


Author: CHEN, Weijie
Contest: ZOJ Monthly, December 2013
Submit    Status