Problem Description

A team of $k$ workers ($1 \leq k \leq 100$) needs to paint a fence consisting of $N$ wooden boards, numbered from left to right as $1$ to $N$ ($1 \leq N \leq 16,000$). Each worker $i$ ($1 \leq i \leq k$) should sit in front of board $S_i$. He can only paint one continuous interval (meaning the boards in the interval must be consecutive). This interval must contain board $S_i$ (in particular, the interval may also be empty, i.e., a worker may choose not to work). In addition, the number of boards painted by worker $i$ must not exceed $L_i$, and he earns $P_i$ dollars for each board he paints ($1 \leq P_i \leq 10,000$). Each board can be painted by at most one worker. All $S_i$ are distinct.

As the team leader, you need to decide the interval each worker should paint and make sure the total income is maximized. The total income is the sum of all workers' individual incomes.

Write a program to determine the maximum possible total income earned by the $k$ workers.

Note: you do not have to paint all boards.

Input Format

The first line of input contains two positive integers $N, k$.

The next $k$ lines each contain three positive integers $L_i, P_i, S_i$.

Output Format

Output one integer, representing the maximum total income.

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

17

Hint

Translated by ChatGPT 5