Optimal Volunteer Recruitment

After successfully winning the bid for the Olympics, Bubu eventually became the head of the Human Resources Department of an Olympic Committee subsidiary company. His first challenge was recruiting short‐term volunteers for a new Olympic project. The project lasts for \(n\) days, and on the \(i\)th day at least \(a_i\) volunteers are needed.

Bubu has learned that there are \(m\) categories of volunteers available for recruitment. A volunteer of the \(j\)th category can work from day \(s_j\) to day \(t_j\) (both inclusive), and recruiting one volunteer of this category costs \(c_j\) yuan. Bubu wants to accomplish the recruitment with the minimum possible cost such that the daily volunteer requirements are met. Your task is to help him design an optimal recruitment plan.

Note: You may assume that an unlimited number of volunteers can be recruited for each category.

Mathematical Formulation:

Find non-negative integers \(x_1, x_2, \ldots, x_m\) (possibly zero) representing the number of volunteers recruited from each category such that for every day \(i\) (\(1 \le i \le n\)),

\[ \sum_{\substack{j=1 \\ s_j \le i \le t_j}} x_j \ge a_i, \]

and the total cost

\[ \sum_{j=1}^m c_j \cdot x_j \]

is minimized.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)), representing the number of days and the number of volunteer categories, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\)), where \(a_i\) is the minimum number of volunteers required on day \(i\).

Each of the next \(m\) lines contains three integers \(s_j\), \(t_j\) and \(c_j\) (\(1 \le s_j \le t_j \le n\), \(1 \le c_j \le 10^9\)), describing a volunteer category that can work from day \(s_j\) to day \(t_j\) with cost \(c_j\) per volunteer.

outputFormat

Output a single integer, the minimum total recruitment cost to meet the volunteer requirements for all \(n\) days.

sample

3 2
1 2 1
1 3 3
2 3 1

4