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