[HNOI2002]情人节礼物

题目描述

明天就是2月14日的了。本来是一件令人高兴地事,但 John却为明天的情人节礼物而非常烦恼。John走遍了各个商店,但没有一件礼物能使他满意的,他觉得那些都缺乏新意。 正当他将要失去信心时,电视中的一个节目引起了他的注意。“这里是XX电视台,明天就是情人节了,我们的《快乐周末》将在明天推出情人节特别节目《鲜花献给有情人》,请各位观众赶快拨打我们的电话,前30对拨打的观众将会有机会在现场参加我们的节目。我们这次节目的内容有•••”其中有一个节目是:主持人将从天上撒下许多鲜花,而参加节目的观众可以推着一个小车,来回移动以接住这些鲜花,最后将根据你所得到的鲜花决定获得的奖励,而你所获得的鲜花也可以全部归自己所有,送给自己心爱的人。奖品倒是无所谓,John知道他的女朋友是很喜欢鲜花的,特别是有这么多各式各样的品种。John于是马上拨打了电视台的号码。竟然刚好是第30位,他太幸运了。 为了珍惜这次难得的机会,John发誓他一定要获得大奖。 通过对这个节目过程的分析,John发现节目的场地可以划分成1\*N个方格,一开始你将站在第N div 2个方格内。每个时刻都可能有鲜花落下,而一旦鲜花落地,你将不能把它捡起来放进小车内。由于小车有一定的重量,控制时并不是特别容易,你在每一时间单位内只能让小车的速度加1,减1或者不变。假设你当前的位置是5,速度是7,下一时间单位你的位置将只能是11,12或者13,对应的速度将分别是6,7,8。与此同时,每朵鲜花也有着不同的分值。获得最高的分值总和就是最终的目的。

输入输出格式

输入格式


输入文件为flower.in,文件的第一行有三个整数N,M,V(N<=100,M<=1000000,1<=V<=5),分别表示场地的宽的度和掉落鲜花数和移动速度。 接下来M行,每行有三个整数i,j,k,按照鲜花落地时间的先后顺序,给出了鲜花落地的时间,位置和分值。

输出格式


输出文件为flower.out,第一行为你的程序得到的最大分值总和,接下来每行有一个整数,表示每一个时刻你的移动速度。 注意:同一时刻可能会有若干朵鲜花落到同一个位置,所有鲜花落到地面的时刻小于或等于10000时间单位。

输入输出样例

输入样例 #1

10 4 3
1 4 2
2 8 10
2 3 10
3 9 10

输出样例 #1

20
1
2
1