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.