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