В популярной экшен-игре в магазине продаются $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