Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
129 - ZOJ Monthly, December 2013 - I
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.

```4 1
1 2 3 4
2 3 4
```

```18
```

#### Hint

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

Author: CHEN, Weijie
Submit    Status