题目描述

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

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

高橋君は $0$ 以上の実数 $t$ を自由に選び、時刻 $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$

输出格式

答えを出力せよ。

题目大意

题目描述

有 $n$ 条鱼在数轴上移动。

第 $i$ 条鱼在时刻 $0$ 时在位置 $x_i$ 处，价值为 $w_i$，将会以每时刻 $t_i$ 的速度向数轴正方向前进。

你是一个渔夫，你有感应河流的能力，你已经知晓所有鱼的 $x,w,t$ 属性。

你会选择一个时刻 $t$，在位置 $x$ 撒下一张长度为 $a$ 的网，所有在时刻 $t$ 时处于区间 $[x,x+a]$ 的鱼都会被你捕获。

你想求出你撒一次网能捕获的鱼的价值和的最大值。

输入格式

第一行两个整数 $n,a$，含义如题中所述。

接下来 $n$ 行，第 $i+1$ 行三个整数，表示第 $i$ 条鱼的 $w,x,t$ 属性。

输出格式

一行一个整数，表示答案。

数据范围与提示

对于所有数据，$1\leq n\leq 2\times 10^3,1\leq a,w_i,x_i,t_i\leq 10^4$。

Translate by Zek3L.

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$
• 入力は全て整数

Sample Explanation 1

時刻 $0.25$ に魚 $1,2,3$ はそれぞれ座標 $25,\ 17.5,\ 22.5$ にいます。よって、この時刻に $x=16$ として行動すると全ての魚を捕まえることができます。

Sample Explanation 2

時刻 $0$ に $x=100$ として行動するのが最適解の一つです。

Sample Explanation 3

時刻 $1$ に $x=100$ として行動するのが最適解の一つです。