#2131. 免费的馅饼

内存限制:259 MiB 时间限制:10 Sec

题目描述

输入格式

第一行是用空格隔开的二个正整数,分别给出了舞台的宽度W(1到10^8之间)和馅饼的个数n(1到10^5)。  接下来n行,每一行给出了一块馅饼的信息。由三个正整数组成,分别表示了每个馅饼落到舞台上的时刻t[i](1到10^8秒),掉到舞台上的格子的编号p[i](1和w之间),以及分值v[i](1到1000之间)。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。

输出格式

一个数,表示游戏者获得的最大总得分。

样例

样例输入


			
3 4
1 2 3
5 2 3
6 3 4
1 1 5

样例输出


			
12
【数据规模】
对于100%的数据,1<=w,t[i]<=10^8,1<=n<=100000。

数据范围与提示