Universal Cup Judging System

Universal Cup

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

Grammy has two teammates A and B. Usually, the two teammates go out to eat at nice restaurants every day, while Grammy generally eats at the school cafeteria. Eating at the school cafeteria saves time and money, while going out sometimes incurs taxi fares. Even so, there are times when Grammy chooses to go out with her teammates to improve her meals.

As the end of the month approaches, Grammy has only $m$ yuan left for her living expenses, and she needs to pass the next $n$ days with this money. On the $i$-th day, she has two choices:

  • Eat at the cafeteria, gaining a satisfaction of $a_i$ and spending $b_i$ yuan.
  • Go out to eat with her teammates, gaining a satisfaction of $c_i$ and spending $d_i$ yuan.

Since A and B go out to eat every day, there will be taxi fares each day. Let $e_i$ be the taxi fare on the $i$-th day, the three of them have established a rule for paying the taxi fare:

  • If Grammy does not go out to eat on the $i$-th day, then there is a $\frac{p_i}{100}$ probability that A will pay for the taxi fare, and a $(1 - \frac{p_i}{100})$ probability that B will pay.
  • If Grammy goes out to eat on the $i$-th day, and since the last time Grammy paid for the taxi fare (or since the first day, if Grammy has never paid for the taxi fare), both A and B have each paid for the taxi fare at least once (regardless of whether Grammy went out to eat at that time), then Grammy will pay for the taxi fare this time. Otherwise, one of the teammates will pay according to the previous rule.

Each day, Grammy will choose her action before the meal. She will know who paid the taxi fare on the previous day, and her goal is to maximize the expected total satisfaction, while ensuring that the total expenses do not exceed $m$ yuan in the worst-case scenario. If she makes optimal decisions every day, what is the expected value of the total satisfaction?

Input

There is only one test case in each test file.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), indicating the number of days and the total expense limit.

For the following $n$ lines, the $i$-th line contains six integers $a_i$, $b_i$, $c_i$, $d_i$, $e_i$, and $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$). Their meanings are described above.

Output

Output one line containing one single number, indicating the maximum expected value of total satisfaction. If there does not exist a plan where the total expenses will be less than or equal to $m$ yuan in the worst-case scenario, output $-1$.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally speaking, suppose that your output is $a$ and the jury's answer is $b$, your output is accepted if and only if $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Examples

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.