接金币游戏

小J最近开始玩一个益智游戏名字叫接金币游戏,游戏的规则是：在一个长度为n的街道上，天上时不时就会掉下金币在街道上，但是当金币碰到地面的一瞬间，那么他就消失了，所以当它出现的时候，你必须刚好站在它下面你才能接到他，然后你一开始的时候在街道的v位置，认为此时是第0秒，你的移动速度是1，即你每秒可以选择呆在原地，或者向左或者向右走一步，同时你还有一瓶兴奋药，当你喝下药水以后，你就获得新生，你的移动速度变成了2，但是兴奋药的持续时间只能维持t秒，t秒过后你又只能移动一步了。
现总共有m个金币会从天上掉下，并且告诉你每个金币掉下来的时间q（第q秒的时候掉下来），掉下来的位置w（在位置w落下）以及这个金币的价值e。
请选择一个最优策略，使得最后接到的金币最大。
其中 1<= n <= 1000 ,1 <= m <= n*n, 1 <= v <= n, 0 <= t <= 10
1 <= q <= 1000, 1 <= w <= n, 1 <= e <= 1000

多组输入，每组数据第一行4个整数分别为n, m, v, t
接下来m行，每行3个整数，分别为q, w, e

每组数据输出一行，表示最多能捡的金币数量

5 5 1 2
1 1 1
1 2 4
1 3 5
1 4 2
1 5 1
5 10 1 2
1 2 4
4 4 8
3 2 4
1 2 1
1 2 7
1 1 4
2 3 2
2 1 6
3 2 6
1 3 9

5
36

Close | Top

Administration