题目描述

一组由 $k$（$1 \leq k \leq 100$） 名工人组成的团队需要粉刷一堵包含 $N$ 个木板的围栏，这些木板从左到右编号为 $1$ 到 $N$（$1 \leq N \leq 16,000$）。每个工人 $i$（$1 \leq i \leq k$）应该坐在木板 $S_i$ 前，他只能粉刷一个连续的区间（这意味着区间内的木板应该是连续的）。这个区间必须包含木板 $S_i$。此外，每个工人粉刷的木板数量不能超过 $L_i$ 个，并且每粉刷一个木板他会得到 $P_i$ 美元（$1 \leq P_i \leq 10,000$）。每个木板最多只能由一个工人粉刷。所有的 $S_i$ 都是不同的。

作为团队的领导者，你需要为每个工人确定他们应该粉刷的区间，并且确保总收入最大化。总收入代表工人个人收入的总和。

编写一个程序来确定 $k$ 名工人获得的总最大收入。

输入格式

输入的第一行是是两个正整数 $N,k$。

接下来 $k$ 行，每行三个正整数 $L_i,P_i,S_i$。

输出格式

输出一个整数，表示总最大收入。

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

17