分数: 500 点
问题陈述
在数轴上,有 N 鱼儿游动。
鱼 i,其权重为 W_i,位于坐标处 X_i 时间 0 并以以下速度移动 V_i 正方向。
Takahashi 将选择任意实数 t 大于或等于 0 并及时执行以下操作 t 一次。
操作:选择任意实数 x。捕获坐标在 之间的所有鱼 x 和 x+A,包括在内。
求他能捕获的鱼的最大总重量。
约束
- 1 \leq N \leq 2000
- 1 \leq A \leq 10^4
- 1 \leq W_i\leq 10^4
- 0 \leq X_i\leq 10^4
- 1 \leq V_i\leq 10^4
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A W_1 X_1 V_1 W_2 X_2 V_2 \vdots W_N X_N V_N
输出
打印答案。
示例输入 1
3 10 100 0 100 1 10 30 10 20 10
示例输出 1
111
时间 0.25, 鱼 1, 2,和 3 位于坐标处 分别是 25, 17.5,和 22.5。因此,此时完成的操作 x=16 捕获了所有的鱼。
示例输入 2
3 10 100 100 100 1 10 30 10 20 10
示例输出 2
100
一个最佳选择是在某个时间执行该操作 0 与 x=100.
示例输入 3
4 10 1000 100 10 100 99 1 10 0 100 1 1 1
示例输出 3
1110
一个最佳选择是在某个时间执行该操作 1 与 x=100.