### National Olympiad in Informatics, China, 2008

## Day 1, Problem 3 - Hiring Employees

After the successful Olympic bid, BuBu's unremitting efforts finally landed him a position as the head of the human resources department for a subsidiary company of the Olympic committee. It's BuBu first day of work and he already encountered a challenging problem: recruit a group of short-term employees for a new Olympic project. After some estimation, it is known that this project will require `N` days to complete, during which, day `i` will require at least `A _{i}` employees.

BuBu learned that a total of `M` types of employees are up for hire. Type `i` employees will work from day `S _{i}` to day

`T`, and must be paid a total of

_{i}`C`dollars. A new broom sweeps clean, so to prove that he can do an astounding job, BuBu wishes to use the minimum possible cost to hire enough employees. This is really not his strength, so BuBu has found you! He hopes that you can help him design an optimal hiring scheme.

_{i}### Input Format

The first line contains two integers `N` and `M`, representing the number days required to complete the project and the number of types of employees up for hire.

The second line will contain `N` nonnegative integers, representing the minimum number of employees needed for each day.

For the following `M` lines, each line will contain three integers `S _{i}`,

`T`, and

_{i}`C`, describing one type of employee. Their meanings are outlined above. For the sake of simplicity, we can assume that there will be an unlimited number of employees for each type.

_{i}### Output Format

Output a single line with a single integer, the cost of the optimal hiring scheme.

### Sample Input

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

### Sample Output

14

### Explanation

Hire 3 type-1 employees and 4 type-3 employees.

### Constraints

For 30% of the test cases, 1 ≤ `N`, `M` ≤ 10, and 1 ≤ `A _{i}` ≤ 10.

For 100% of the test cases, 1 ≤

`N`≤ 1000, and 1 ≤

`M`≤ 10000. Also, other values in the data will not exceed 2

^{31}− 1.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 128M

**Added:** Aug 01, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...