Hiring Employees

Time limit1sMemory limit256 MB

Summary

Given the daily minimum headcount and employee types that each work a range of consecutive days at a fixed cost, find the cheapest hiring plan that covers every day.

Level: Medium7 of 10
Topics: Shortest path, Intervals, Graph
Solved: No attempts yet

Problem

After the successful Olympic bid, BuBu worked his way up to head of the human resources department at a subsidiary of the Olympic committee. On his first day, he faced a hard problem: hire a group of short-term employees for a new Olympic project. A rough estimate shows the project takes $N$ days, and on day $i$ it needs at least $A_i$ employees.

A total of $M$ employee types are available for hire. Type $i$ employees work from day $S_i$ to day $T_i$ , and each costs $C_i$ dollars. BuBu wants enough employees on every day at the lowest possible total cost. Help him find the optimal hiring plan. There is no limit on how many employees of each type can be hired.

Input

The first line contains two integers $N$ and $M$ .

The second line contains $N$ nonnegative integers, $A_1, A_2, \ldots, A_N$ .

Each of the next $M$ lines contains three integers $S_i$ , $T_i$ , and $C_i$ , describing one employee type.

Output

Print a single line containing one integer, the cost of the optimal hiring plan.

Constraints

$1 \le N \le 1000$

$1 \le M \le 10000$

All other values in the input do not exceed $2^{31} - 1$ .

Examples1

Example 1
Input
```
3 3
2 3 4
1 2 2
2 3 5
3 3 2
```
Expected output
```
14
```