Score : $500$ points

问题描述

在数轴上，有 $N$ 条鱼在游动。

第 $i$ 条鱼的重量为 $W_i$，在时间 $0$ 时刻位于坐标 $X_i$ 处，并以速度 $V_i$ 向正方向移动。

高桥将选择一个大于等于 $0$ 的任意实数 $t$，并在时间 $t$ 仅执行一次以下动作：

动作：选择一个任意实数 $x$。捕获所有坐标位于 $x$ 和 $x+A$（包含两端点）之间的鱼。

请找出他能捕获的最大总重量的鱼。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

On a number line, there are $N$ fish swimming.

Fish $i$, which has a weight of $W_i$, is at the coordinate $X_i$ at time $0$ and moves at a speed of $V_i$ in the positive direction.

Takahashi will choose an arbitrary real number $t$ greater than or equal to $0$ and do the following action at time $t$ just once.
Action: Choose an arbitrary real number $x$. Catch all fish whose coordinates are between $x$ and $x+A$, inclusive.

Find the maximum total weight of fish that he can catch.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A$

$W_1$ $X_1$ $V_1$

$W_2$ $X_2$ $V_2$

$\vdots$

$W_N$ $X_N$ $V_N$

Output

Print the answer.

Sample Input 1

3 10
100 0 100
1 10 30
10 20 10

Sample Output 1

111

At time $0.25$, fish $1$, $2$, and $3$ are at the coordinates $25$, $17.5$, and $22.5$, respectively. Thus, the action done at this time with $x=16$ catches all the fish.

Sample Input 2

3 10
100 100 100
1 10 30
10 20 10

Sample Output 2

100

One optimal choice is to do the action at time $0$ with $x=100$.

Sample Input 3

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

Sample Output 3

1110

One optimal choice is to do the action at time $1$ with $x=100$.

update @ 2024/3/10 11:33:14