P3337 [ZJOI2013] Defensive Frontline

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.

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 a single line with one number: the minimum cost.

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