The battle line can be viewed as a sequence of length $n$. We need to build towers on this sequence to defend against enemy soldiers. Building a tower at position $i$ costs $C_i$, and any number of towers can be built at a single position, with costs being additive. There are $m$ intervals $[L_1, R_1], [L_2, R_2], \dots, [L_m, R_m]$, and at least $D_i$ towers must be built within the range of the $i$-th interval. Find the minimum cost.

Input

The first line contains two integers $n$ and $m$. The next line contains $n$ integers, describing the array $C$. The next $m$ lines each contain three integers $L_i, R_i, D_i$, describing an interval.

Output

A single line containing one integer, the minimum cost.

Examples

Input 1

5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2

Output 1

11

Note

Build 2 towers at position 1, 1 tower at position 3, and 1 tower at position 4. The cost is $1 \times 2 + 6 + 3 = 11$.

Constraints

• For 20% of the data, $n \le 20, m \le 20$.
• For 50% of the data (including the above), all $D_i = 1$.
• For 70% of the data (including the above), $n \le 100, m \le 1000$.
• For 100% of the data, $n \le 1000, m \le 10000$, $1 \le L_i \le R_i \le n$, and all other data are $\le 10000$.