bzoj#P2131. 免费的馅饼

免费的馅饼

题目描述

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

在这里插入图片描述

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

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

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

输入格式

第一行是用空格隔开的两个正整数,分别给出了舞台的宽度 ww 和馅饼的个数 nn

接下来 nn 行,每一行给出了一块馅饼的信息。由三个正整数组成,分别表示了每个馅饼落到舞台上的时刻 tit_i,掉到舞台上的格子的编号 pip_i,以及分值 viv_i

游戏开始时刻为 00 。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的 tit_ipip_i 都一样。

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,1w1081\le w\le 10^81n1051\le n \le 10^51ti1081\le t_i\le 10^81piw1\le p_i\le w1vi1031\le v_i\le 10^3