问题描述

有 $K$ 个工人和 $N$ 块连续的木板。每个工人有三个参数：

• $L_i$：最多可粉刷的连续木板数（必须包含其位置 $S_i$）
• $P_i$：粉刷一块木板可获得的工钱
• $S_i$：工人初始位置（不可移动）

每个工人可选择不粉刷，或粉刷一段包含 $S_i$ 的、长度不超过 $L_i$ 的连续木板（每块木板最多被刷一次）。求所有工人能获得的最大总工钱。

输入格式

• 第一行：$N$（木板数，$1 \le N \le 16,000$）、$K$（工人数，$1 \le K \le 100$）
• 接下来 $K$ 行：每行 $L_i, P_i, S_i$（$1 \le L_i \le N, 1 \le P_i \le 10,000, 1 \le S_i \le N$）

输出格式

• 一个整数：最大总工钱

示例1

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

17

SOURCE

poj1821