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 `a`_{i}). After that, there are `Q` triples of integers (`l`_{i}, `r`_{i}, `c`_{i}) (`i`=1..`Q`) which describe the salary increasing in chronological.

1 ≤ `n` ≤ 10^{5} , 1 ≤ `Q` ≤ 10^{5} , 1 ≤ `a`_{i} ≤ 10^{5} , 1 ≤ `l`_{i} ≤ `r`_{i} ≤ 10^{5} , 1 ≤ `c`_{i} ≤ 10^{5} , `r`_{i} < `l`_{i+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