في لعبة حركة شهيرة، توجد $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