题目描述

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

第 $i$ 条鱼的初始重量为 $W_i$，初始坐标为 $X_i$，速度为 $V_i$，且向正方向移动。

Takahashi 可以选择一个大于等于 $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$。