题目描述

驴认为薯片是最好的食物！

所以今天，当他决定去长途旅行时，他希望他的背包里装满各种薯片。他在家里的零食区寻找，发现了很多薯片。

为了更好地决定带哪些薯片（可能是总袋数的一个子集，也可以是空集），他定义了薯片的属性如下：

• $h_i$：这袋薯片能给驴带来的快乐。
• $s_i$：这袋薯片占据的空间。
• $d_i$：这袋薯片的易碎度。

为了解问题，我们将 $h_i, s_i, d_i$ 记作这袋薯片的快乐度、空间量和易碎度。因为背包有大小，所以所选袋子的总占用空间不能超过背包的容量 $V$。

然而，薯片的易碎可能在旅途中造成颠簸，进一步导致价值损失。如果选择的薯片是所有薯片的一个非空子集，包含了第 $i_1, i_2, ..., i_k$ ($k \geq 1$) 包，而未占用的空间是 $U$，则由于颠簸造成的总价值损失为 $(d_{i_1} + d_{i_2} + ... + d_{i_k}) \times U$。特别的，不选择任何一包薯片的情况下不会产生任何价值损失。

考虑到薯片的利与弊，整个背包的价值定义为这些薯片带来的总快乐值减去总价值损失。驴要最大化这个值，但就是无法做出决定。需要帮助！

输入格式

每组测试包含多个测试用例。

• 第一行包含测试用例的数量 $T \ (1 \leq T \leq 10^4)$。

每个测试用例如下：

• 第一行包含 $2$ 个整数 $n, V \ (1 \leq n \leq 10^5, 1 \leq V \leq 500)$，薯片袋的数量和背包的总容量。
• 从第 $2$ 行到第 $n+1$ 行，每行包含 3 个整数 $h_i, s_i, d_i \ (1 \leq s_i \leq 500, 1 \leq h_i, d_i \leq 10^9)$，第 $i$ 袋薯片的快乐度、空间量和易碎度。

保证在单组测试中，所有测试用例的 $\sum n \leq 10^5$，且所有测试用例的 $\sum V^2 \leq 2.5 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数——价值的最大值。

2
2 5
10 2 1
2 2 100
2 10
10 2 1
2 3 100

7
12

解释 #1

对于第一个测试用例中，驴选择第一袋，导致价值为：

$10 - (5 - 2) \times 1 = 7$

在第二个测试用例中，驴选择第一袋和第二袋，导致价值为：

$10 + 2 - (5 - 2 - 3) \times (1 + 100) = 12$

可以证明没有更好的策略。