У Грэмми есть два сокомандника — 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