Grammy 有兩個隊友 A 同 B。平時,呢兩個隊友每日都會出去好餐廳食飯,而 Grammy 通常會喺學校飯堂食。喺學校飯堂食可以慳時間同埋慳錢,而出街食有時仲要搭的士。就算係噉,Grammy 有時都會揀同隊友一齊出街食,改善一下伙食。
臨近月底,Grammy 淨係得返 $m$ 元生活費,佢需要靠呢筆錢過埋接落嚟嘅 $n$ 日。喺第 $i$ 日,佢有兩個選擇:
- 喺飯堂食,獲得 $a_i$ 點滿足感,並花費 $b_i$ 元。
- 同隊友一齊出街食,獲得 $c_i$ 點滿足感,並花費 $d_i$ 元。
因為 A 同 B 每日都會出街食飯,所以每日都會有的士車資。設第 $i$ 日嘅的士車資為 $e_i$,佢哋三個人制定咗一條畀的士錢嘅規則:
- 如果 Grammy 喺第 $i$ 日冇出街食飯,咁就有 $\frac{p_i}{100}$ 嘅機率由 A 畀的士錢,以及 $(1 - \frac{p_i}{100})$ 嘅機率由 B 畀。
- 如果 Grammy 喺第 $i$ 日出街食飯,而且自從 Grammy 上一次畀的士錢以嚟(如果 Grammy 從來未畀過的士錢,就自從第一日以嚟),A 同 B 各自都至少畀過一次的士錢(無論當時 Grammy 有冇一齊出街食),咁今次就由 Grammy 畀的士錢。否則,就會由其中一位隊友按照上一條規則畀錢。
每日食飯之前,Grammy 都會揀定佢嘅行動。佢會知道前一日係邊個畀的士錢,而佢嘅目標係喺保證最壞情況下總花費唔超過 $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