Description

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

Input Format

The first line contains two numbers $n, m$.

The next line contains $n$ numbers, describing the $C$ array.

The next $m$ lines each contain three numbers $L_i, R_i, D_i$, describing an interval.

Output Format

Output a single line with one number: the minimum cost.

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

11

Hint

Sample explanation:

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

Constraints:

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

Translated by ChatGPT 5