1841. [国家集训队2011]免费的馅饼(加强版)

【题目描述】

SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为w格（从左到右依次用1到w编号），游戏者占一格。开始时游戏者可以站在舞台的任意位置，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。

当馅饼在某一时刻恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。当馅饼落在一个游戏者不在的格子里时该馅饼就消失。

写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。大样例

【输入格式】

输入文件的第一行是用空格隔开的二个正整数，分别给出了舞台的宽度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

【提示】

约30%的数据，1 ≤ w, n, t[i] ≤ 1000；

约70%的数据，1 ≤ w, t[i] ≤ 10^8；1 ≤ n ≤ 10000；

对于100%的数据，1 ≤ w, t[i] ≤ 10^8；1 ≤ n ≤ 100000。

【来源】

国家集训队2011 李其乐