У Греммі є два співкомандники — A та B. Зазвичай ці два співкомандники щодня ходять їсти до гарних ресторанів, тоді як Греммі здебільшого їсть у шкільній їдальні. Харчування у шкільній їдальні заощаджує час і гроші, а походи до ресторану іноді потребують витрат на таксі. Проте бувають дні, коли Греммі вирішує піти поїсти разом зі співкомандниками, щоб покращити свій раціон.
Наближається кінець місяця, і у Греммі залишилося лише $m$ юанів на проживання, з якими їй потрібно прожити наступні $n$ днів. У $i$-й день вона має два варіанти:
- Поїсти в їдальні, отримавши задоволення $a_i$ і витративши $b_i$ юанів.
- Піти поїсти зі співкомандниками, отримавши задоволення $c_i$ і витративши $d_i$ юанів.
Оскільки A і B ходять їсти щодня, витрати на таксі виникають кожного дня. Нехай $e_i$ — вартість таксі в $i$-й день; вони втрьох встановили таке правило оплати таксі:
- Якщо Греммі не йде їсти з ними в $i$-й день, то з імовірністю $\frac{p_i}{100}$ за таксі заплатить A, а з імовірністю $(1 - \frac{p_i}{100})$ заплатить B.
- Якщо Греммі йде їсти з ними в $i$-й день, і з того часу, як Греммі востаннє платила за таксі (або з першого дня, якщо Греммі ще жодного разу не платила за таксі), і A, і B хоча б по одному разу заплатили за таксі (незалежно від того, чи ходила тоді Греммі з ними), то цього разу за таксі платить Греммі. Інакше за таксі заплатить один зі співкомандників за попереднім правилом.
Щодня Греммі обирає свою дію перед їжею. Вона знає, хто платив за таксі попереднього дня, а її мета — максимізувати математичне сподівання сумарного задоволення, гарантуючи при цьому, що в найгіршому випадку загальні витрати не перевищать $m$ юанів. Яким буде математичне сподівання сумарного задоволення, якщо щодня вона приймає оптимальні рішення?
Вхідні дані
У кожному тестовому файлі міститься лише один набір вхідних даних.
Перший рядок містить два цілі числа $n$ і $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$) — кількість днів та ліміт загальних витрат.
У наступних $n$ рядках $i$-й рядок містить шість цілих чисел $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ та $p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$). Їхні значення описані вище.
Вихідні дані
Виведіть один рядок, що містить одне число — максимальне математичне сподівання сумарного задоволення. Якщо не існує плану, за якого загальні витрати в найгіршому випадку не перевищують $m$ юанів, виведіть $-1$.
Ваша відповідь вважатиметься правильною, якщо її абсолютна або відносна похибка не перевищує $10^{-6}$. Формально кажучи, припустімо, що ваш вивід дорівнює $a$, а відповідь журі дорівнює $b$; ваш вивід приймається тоді й лише тоді, коли $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Приклади
2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1