Танымал экшен-ойында дүкенде критикалық соққыға арналған $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$-ші жолда $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$) берілген.

Барлық тест жиынтықтары бойынша $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