Fence

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

一支由 $k$ 名工人组成的团队需要粉刷一堵含有 $N$ 块木板的围栏，木板从左到右编号为 $1$ 到 $N$。

工人 $i$ 坐在木板 $S_i$ 前。他可以不工作；若工作，则只能粉刷一个包含 $S_i$ 的连续非空区间，且区间长度不超过 $L_i$。他每粉刷一块木板可获得 $P_i$ 美元。每块木板至多由一名工人粉刷，所有 $S_i$ 两两不同。

请为每名工人确定粉刷区间，使总收入最大。你不必粉刷全部木板。

输入格式

第一行输入两个正整数 $N,k$。接下来 $k$ 行，第 $i$ 行输入三个正整数 $L_i,P_i,S_i$。

输出格式

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

样例输入

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

样例输出

17

数据范围

对于所有数据，$1\le N\le16000$，$1\le k\le100$，$1\le L_i\le N$，$1\le P_i\le10000$，$1\le S_i\le N$，且所有 $S_i$ 两两不同。由此必有 $k\le N$。

原题只要求 $L_i$ 为正整数；当 $L_i>N$ 时，将其替换为 $N$ 不改变任何可行方案，因此这里采用上述等价范围。