Trong một trò chơi hành động phổ biến, có $n$ trang bị chí mạng khác nhau được bán trong cửa hàng. Trang bị thứ $i$ có xác suất $\frac{p_i}{100}$ kích hoạt đòn chí mạng với hệ số nhân $v_i$, và có giá $w_i$ xu. Mỗi trang bị chỉ có thể được mua tối đa một lần.

Khi nhiều trang bị kích hoạt đòn chí mạng cùng lúc, chỉ có hệ số nhân cao nhất mới có hiệu lực. Nếu không có trang bị nào kích hoạt đòn chí mạng, hệ số nhân hiệu dụng được coi là $0$.

Bạn có thể chi tối đa $m$ xu để mua một số trang bị. Bạn cần tối đa hóa kỳ vọng của hệ số nhân hiệu dụng từ các trang bị đã mua.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 300$), cho biết số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 3 \times 10^3$), cho biết số lượng trang bị và số xu tối đa bạn có thể chi tiêu.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $p_i$, $v_i$ và $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), mô tả trang bị thứ $i$.

Đảm bảo rằng tổng của $n$ và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $3 \times 10^3$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số thực duy nhất, cho biết kỳ vọng hệ số nhân hiệu dụng lớn nhất.

Câu trả lời của bạn sẽ được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$. Nói một cách hình thức, giả sử câu trả lời của bạn là $a$ và đáp án của ban giám khảo là $b$, câu trả lời của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

68.750000000000
0.000000000000