Description

在一款热门动作游戏中，商店里共有 $n$ 种不同的暴击装备。 第 $i$ 件装备有 $\dfrac{p_i}{100}$ 的概率触发暴击，暴击倍率为 $v_i$，购买花费 $w_i$ 金币。每件装备仅可购买一次。

当多件装备同时触发暴击时，仅倍率最高的暴击生效。 若没有任何装备触发暴击，则等效倍率视为 $0$。

你最多可以花费 $m$ 枚金币选购若干装备，请求出选购装备后，等效暴击倍率的最大数学期望。

Format

Input

本题包含多组测试用例。 第一行输入一个整数 $T\ (1 \le T \le 300)$，代表测试用例组数。

对于每组测试用例： 第一行输入两个整数 $n,m\ (1\le n,m \le 3\times 10^3)$，分别表示装备数量与最大可花费金币数。 接下来 $n$ 行，每行输入三个整数 $p_i,v_i,w_i$ $(1\le p_i\le 100,\ 1\le v_i\le 10^9,\ 1\le w_i\le 3\times 10^3)$，依次代表该装备的暴击概率、暴击倍率、购买花费。

保证所有测试用例的 $n$ 总和、$m$ 总和均不超过 $3\times 10^3$。

Output

每组测试用例输出一行实数，表示最大等效暴击倍率期望。

答案满足绝对误差或相对误差不超过 $10^{-6}$ 即判定正确。 形式化说明：设你的答案为 $a$，标准答案为 $b$，当且仅当

时，答案视为合法。

Samples

2
3 15
75 50 5
50 100 10
25 200 15
2 10
50 10
50 10 100
70 30 1000

68.750000000000
0.000000000000

Limitation

1s, 1024KiB for each test case.