Description

After the successful Olympic bid, through persistent effort, Bubu finally became the head of the HR department of a company under the Organizing Committee. On his first day, he faced a challenge: recruiting a group of short-term volunteers for a new Olympic project. It is estimated that the project will take $n$ days to complete, and on day $i$, at least $a_i$ people are needed.

There are $m$ types of volunteers available. Type $i$ can work from day $s_i$ to day $t_i$ (inclusive), and the recruitment cost is $c_i$ yuan per person. Eager to excel in his new role, Bubu wants to recruit enough volunteers at the minimum possible cost, but this is not his strong suit. He turns to you to design an optimal recruitment plan.

For convenience, assume the number of volunteers of each type is unlimited. It is guaranteed that there exists a feasible recruitment plan.

Input Format

• The first line contains two integers $n, m$, denoting the number of days needed to complete the project and the number of available volunteer types.
• The second line contains $n$ non-negative integers, denoting the minimum number of volunteers required for each day.
• Each of the next $m$ lines contains three integers $s_i, t_i, c_i$, as described above.

Output Format

Output a single integer, the total cost of your optimal plan.

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

14

Hint

Constraints: $1 \le n \le 1000$, $1 \le m \le 10000$, and all other quantities involved do not exceed $2^{31} - 1$.

Translated by ChatGPT 5