במשחק פעולה פופולרי, ישנם $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