描述

一个由$k$个工人（$1 \leq K \leq 100$）组成的队伍需要粉刷一面包含$N$块栅栏板（编号从1到$N$）的栅栏，从左到右。每个工人$i$（$1 \leq i \leq K$）应该坐在第$S_i$块栅栏板前面，他只能粉刷一个连续的区间（这意味着区间中的栅栏板应该是连续的）。这个区间必须包含$S_i$块栅栏板。同时，每个工人最多只能粉刷$L_i$块栅栏板，并且每粉刷一块栅栏板他会得到$P_i$元（$1 \leq P_i \leq 10000$）。每块栅栏板只能由一个工人粉刷。所有的$S_i$值应该是不同的。

作为队长，你需要确定每个工人应该粉刷哪个区间，以使得总收入最大化。总收入是指工人个人收入的总和。

输入

输入包括：

第一行包含两个整数$N$和$K$。

接下来的$K$行，每行包含三个整数$L_i$、$P_i$和$S_i$，分别表示第$i$个工人最多可以粉刷的栅栏板数、每块栅栏板的收入和该工人坐在的栅栏板位置。

输出

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

输入数据1

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

输出数据1

17

提示

解释：

• 工人1粉刷区间[1, 2]；
• 工人2粉刷区间[3, 4]；
• 工人3粉刷区间[5, 7]；
• 工人4没有粉刷任何栅栏板。

来源
Romania OI 2002