Grammy には A と B という 2 人のチームメイトがいます。普段、2 人のチームメイトは毎日素敵なレストランへ外食に行きますが、Grammy はたいてい学校の食堂で食事をします。学校の食堂で食べると時間とお金を節約できますが、外食するとタクシー代がかかることがあります。それでも、食事を充実させるために Grammy がチームメイトと一緒に外食を選ぶこともあります。
月末が近づき、Grammy の生活費は残り $m$ 元しかなく、このお金で次の $n$ 日間を過ごさなければなりません。$i$ 日目には、彼女には 2 つの選択肢があります:
- 食堂で食事をし、満足度 $a_i$ を得て $b_i$ 元を支払う。
- チームメイトと外食し、満足度 $c_i$ を得て $d_i$ 元を支払う。
A と B は毎日外食するため、毎日タクシー代が発生します。$i$ 日目のタクシー代を $e_i$ とすると、3 人はタクシー代の支払いについて次のルールを定めています:
- $i$ 日目に Grammy が外食しない場合、確率 $\frac{p_i}{100}$ で A がタクシー代を支払い、確率 $(1 - \frac{p_i}{100})$ で B が支払う。
- $i$ 日目に Grammy が外食し、かつ Grammy が最後にタクシー代を支払ってから(Grammy が一度もタクシー代を支払ったことがない場合は 1 日目から)、A と B の両方がそれぞれ少なくとも 1 回ずつタクシー代を支払っている場合(そのときに Grammy が外食したかどうかは問わない)、今回は Grammy がタクシー代を支払う。そうでない場合は、前のルールに従ってチームメイトの 1 人が支払う。
毎日、Grammy は食事の前に自分の行動を選択します。彼女は前日に誰がタクシー代を支払ったかを知っており、最悪のケースでも総支出が $m$ 元を超えないことを保証しつつ、総満足度の期待値を最大化することが目標です。彼女が毎日最適な判断を下すとき、総満足度の期待値はいくらになりますか?
入力
各テストファイルには 1 つのテストケースのみが含まれます。
1 行目には日数と総支出の上限を表す 2 つの整数 $n$ と $m$($1 \le n \le 2 \times 10^3$、$1 \le m \le 5 \times 10^3$)が与えられます。
続く $n$ 行のうち $i$ 行目には、6 つの整数 $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$)が与えられます。それぞれの意味は上記の通りです。
出力
総満足度の最大期待値を表す 1 つの数値を 1 行に出力してください。最悪のケースで総支出が $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