Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.