钓鱼

题目描述

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

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

高桥君将选择一个任意实数 $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

在时刻 $0.25$,鱼 $1$、$2$、$3$ 分别位于坐标 $25$、$17.5$、$22.5$。因此,在这个时刻令 $x=16$ 执行动作,即可抓住所有的鱼。

3 10
100 100 100
1 10 30
10 20 10

100

一种最优做法是在时刻 $0$ 令 $x=100$ 执行动作。

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

1110

一种最优做法是在时刻 $1$ 令 $x=100$ 执行动作。

数据范围

• $1 \le N \le 2000$
• $1 \le A \le 10^4$
• $1 \le W_i \le 10^4$
• $0 \le X_i \le 10^4$
• $1 \le V_i \le 10^4$
• 输入中的所有值均为整数