F - Fishing Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

数直線上を N 匹の魚が泳いでいます。

魚 i の重さは W_i であり、時刻 0 に座標 X_i にいて、正方向に速さ V_i で移動しています。

高橋君は 0 以上の実数 t を自由に選び、時刻 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 として行動するのが最適解の一つです。

Score : 500 points

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.