Migrated from Lutece 3196 高木同学

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

擅长捉弄人(西片)的高木同学又开始给西片出题了。擅长白给的西片同学又信誓旦旦地接下了挑战。

现在他们面前有$n$个顺序排列的白木板。编号为 $1$ 到 $n$ 。

高木给总共西片 $m$ 分钟的时间，对于第 $i$ 分钟，西片可以选择什么都不做，或者，选择给木板涂色。

涂色只能选编号连续的木板涂，而且已经涂过的不能再被涂。在第 $i$ 分钟，西片最多只能涂连续的

$L_i$ 个木板，涂的每个木板得分为 $P_i$ , 而且必须包含编号为 $S_i$ 的木板。

现在高木要西片回答，这 $m$ 分钟后，最多能得多少分。

总是白给的西片可不会这题，于是他向聪明的你求助，请你帮帮他吧，你只需要告诉他答案就行

了。

Input

第一行俩个数 $n$ , $m$ ，分别表示总的木板数量以及总时间。

接下来每行三个整数 $L_i$，$P_i$，$S_i$，意义如题意所诉。

Output

一个整数，表示最大分数。

Samples

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

17

Constraints

$1 \leqslant n \leqslant 16000$ $1 \leqslant m \leqslant 100$ $1 \leqslant P_i \leqslant 10000$ $1 \leqslant L_i ,S_i \leqslant n$ 数据保证 $S_i$ 互不相同

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming