Maximizing Fence Painting Revenue

A team of \( k \) workers (\(1\le k\le 100\)) needs to paint a fence consisting of \( N \) wooden boards numbered from 1 to \( N \) (\(1\le N\le 16000\)). Each worker \(i\) (\(1\le i\le k\)) is seated in front of board \(S_i\) (all \(S_i\)'s are distinct) and must paint a contiguous segment of boards that contains board \(S_i\). The segment for worker \(i\) can have at most \( L_i \) boards and the worker earns \( P_i \) dollars for each board painted. Moreover, no board can be painted by more than one worker.

Your task as the team leader is to assign to each worker a segment satisfying the conditions above so that the total revenue is maximized. The revenue for worker \(i\) who paints boards from \(a_i\) to \(b_i\) will be:

[ \text{Revenue}_i = P_i\times (b_i - a_i + 1), \quad \text{with}\quad a_i \le S_i \le b_i \quad \text{and} \quad b_i - a_i + 1 \le L_i. ]

The segments assigned to different workers must not overlap, i.e. if worker \(i\) is assigned \([a_i,b_i]\) and worker \(j\) is assigned \([a_j,b_j]\) with \(i < j\) (assuming the workers are sorted by \(S_i\)), then \(b_i < a_j\).

Determine the maximum total revenue achievable by an optimal assignment.

inputFormat

The first line contains two integers \(N\) and \(k\), representing the number of boards and the number of workers respectively.

Each of the following \(k\) lines contains three integers \(S_i\), \(L_i\), and \(P_i\): the board at which worker \(i\) is seated, the maximum number of boards worker \(i\) can paint, and the profit per board for worker \(i\), respectively.

outputFormat

Output a single integer – the maximum total revenue that can be achieved.

sample

10 2
3 3 2
7 4 3

18