ある人気のアクションゲームでは、ショップで $n$ 個の異なるクリティカル装備が販売されています。$i$ 番目の装備は確率 $\frac{p_i}{100}$ で倍率 $v_i$ のクリティカルを発動し、価格は $w_i$ コインです。各装備は 1 回しか購入できません。

複数の装備が同時にクリティカルを発動した場合、最も高い倍率のみが有効になります。どの装備もクリティカルを発動しなかった場合、有効倍率は $0$ とみなされます。

あなたは最大で $m$ コインを使っていくつかの装備を購入できます。購入した装備の有効倍率の期待値を最大化してください。

入力

入力は複数のテストケースからなります。入力の 1 行目には、テストケースの数を表す整数 $T$ ($1 \le T \le 300$) が与えられます。各テストケースについて：

1 行目には、装備の数と使用できるコインの最大数を表す 2 つの整数 $n$ と $m$ ($1 \le n, m \le 3 \times 10^3$) が与えられます。

続く $n$ 行のうち $i$ 行目には、$i$ 番目の装備を表す 3 つの整数 $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$ を超えないことが保証されます。

出力

各テストケースについて、有効倍率の期待値の最大値を表す 1 つの実数を 1 行に出力してください。

あなたの出力の絶対誤差または相対誤差が $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