题目描述

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

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

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

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

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

然而，未占用的空间可能在驴旅行时造成颠簸，进一步导致价值损失。如果选择的薯片是所有薯片的一个非空子集，包含了第 $i_1, i_2, \ldots, i_k$ ($k \geq 1$) 包，而未占用的空间是 $U$，则由于颠簸造成的总价值损失为 $(d_{i_1} + d_{i_2} + \cdots + 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$ 不超过 $10^5$，且所有测试用例的 $\sum V^2$ 不超过 $2.5 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示驴能获得的最大价值。

输入输出样例 #1

输入 #1

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

输出 #1

7
12