Fishing

题目描述

在数轴上，有 $N$ 条鱼在游动。 鱼 $i$，重量为 $W_i$，在时间 $0$ 时位于坐标 $X_i$，并以速度 $V_i$ 向正方向移动。 Takahashi 将选择任意实数 $t$（$t \ge 0$），并在时间 $t$ 仅执行以下操作一次。
操作：选择任意实数 $x$。捕获所有坐标在 $x$ 到 $x+A$（包含端点）之间的鱼。 求他能够捕获的鱼的最大总重量。

输入格式

输入由标准输入给出，格式如下： $N$ $A$ $W_1$ $X_1$ $V_1$ $W_2$ $X_2$ $V_2$ $\vdots$ $W_N$ $X_N$ $V_N$

输出格式

输出答案。

3 10
100 0 100
1 10 30
10 20 10

111

3 10
100 100 100
1 10 30
10 20 10

100

4 10
1000 100 10
100 99 1
10 0 100
1 1 1

1110

提示

$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$ 输入中的所有数值均为整数。在时间 $0.25$ 时，鱼 $1$、$2$、$3$ 的坐标分别为 $25$、$17.5$ 和 $22.5$。因此，在该时间以 $x=16$ 进行操作可以捕获所有鱼。
一个最优选择是在时间 $0$ 以 $x=100$ 进行操作。
一个最优选择是在时间 $1$ 以 $x=100$ 进行操作。

标签: AtCoder|abc274F

来源

AtCoder|abc274F