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

当多件装备同时触发暴击时，只有最高的倍率会生效。如果没有装备触发暴击，则实际生效的倍率视为 $0$。

你最多可以花费 $m$ 金币来购买一些装备。你需要最大化所购装备的期望实际生效倍率。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T \le 300$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 3 \times 10^3$)，分别表示装备的数量和你可以花费的最大金币数。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $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$)，表示第 $i$ 件装备。

保证所有测试数据的 $n$ 之和以及 $m$ 之和均不超过 $3 \times 10^3$。

输出格式

对于每组测试数据，输出一行，包含一个实数，表示最大期望实际生效倍率。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。具体来说，假设你的答案为 $a$，评测答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，你的答案才会被接受。

样例

输入 1

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

输出 1

68.750000000000
0.000000000000