Grammy memiliki dua rekan tim, A dan B. Biasanya, kedua rekan tim tersebut pergi makan di restoran bagus setiap hari, sedangkan Grammy umumnya makan di kantin kampus. Makan di kantin kampus menghemat waktu dan uang, sementara makan di luar terkadang membutuhkan ongkos taksi. Meski begitu, ada kalanya Grammy memilih pergi makan bersama rekan timnya untuk menikmati makanan yang lebih enak.
Menjelang akhir bulan, Grammy hanya memiliki sisa uang sebesar $m$ yuan untuk biaya hidupnya, dan ia harus melewati $n$ hari berikutnya dengan uang tersebut. Pada hari ke-$i$, ia memiliki dua pilihan:
- Makan di kantin, memperoleh kepuasan sebesar $a_i$ dan menghabiskan $b_i$ yuan.
- Pergi makan di luar bersama rekan timnya, memperoleh kepuasan sebesar $c_i$ dan menghabiskan $d_i$ yuan.
Karena A dan B pergi makan di luar setiap hari, akan selalu ada ongkos taksi setiap harinya. Misalkan $e_i$ adalah ongkos taksi pada hari ke-$i$, mereka bertiga telah menetapkan aturan pembayaran ongkos taksi:
- Jika Grammy tidak pergi makan di luar pada hari ke-$i$, maka terdapat peluang $\frac{p_i}{100}$ bahwa A yang akan membayar ongkos taksi, dan peluang $(1 - \frac{p_i}{100})$ bahwa B yang akan membayar.
- Jika Grammy pergi makan di luar pada hari ke-$i$, dan sejak terakhir kali Grammy membayar ongkos taksi (atau sejak hari pertama, jika Grammy belum pernah membayar ongkos taksi), baik A maupun B masing-masing telah membayar ongkos taksi setidaknya satu kali (terlepas dari apakah Grammy ikut makan di luar pada saat itu atau tidak), maka kali ini Grammy yang akan membayar ongkos taksi. Jika tidak, salah satu rekan tim akan membayar sesuai aturan sebelumnya.
Setiap hari, Grammy akan memilih tindakannya sebelum makan. Ia mengetahui siapa yang membayar ongkos taksi pada hari sebelumnya, dan tujuannya adalah memaksimalkan nilai harapan total kepuasan, sambil memastikan bahwa total pengeluaran tidak melebihi $m$ yuan dalam skenario terburuk. Jika ia mengambil keputusan optimal setiap hari, berapakah nilai harapan dari total kepuasan?
Masukan
Hanya terdapat satu kasus uji di setiap berkas uji.
Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), yang menyatakan banyaknya hari dan batas total pengeluaran.
Untuk $n$ baris berikutnya, baris ke-$i$ berisi enam bilangan bulat $a_i$, $b_i$, $c_i$, $d_i$, $e_i$, dan $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$). Makna masing-masing variabel telah dijelaskan di atas.
Keluaran
Keluarkan satu baris yang berisi satu bilangan, yang menyatakan nilai harapan maksimum dari total kepuasan. Jika tidak ada rencana yang membuat total pengeluaran kurang dari atau sama dengan $m$ yuan dalam skenario terburuk, keluarkan $-1$.
Jawaban Anda akan dianggap benar jika galat mutlak atau galat relatifnya tidak melebihi $10^{-6}$. Secara formal, misalkan keluaran Anda adalah $a$ dan jawaban juri adalah $b$, keluaran Anda diterima jika dan hanya jika $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Contoh
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