ในเกมแอ็กชันยอดนิยมเกมหนึ่ง มีอุปกรณ์คริติคอลที่แตกต่างกัน $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