← 返回题目列表

AtCoder · abc274_f

I. 钓鱼

中文机器翻译题面 查看原题

分数: 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.