Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

У Греммі є два співкомандники — 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.