Grammy có hai người đồng đội là A và B. Thông thường, hai người đồng đội ngày nào cũng ra ngoài ăn ở những nhà hàng ngon, còn Grammy thường ăn tại căng tin trường. Ăn ở căng tin trường giúp tiết kiệm thời gian và tiền bạc, trong khi ra ngoài ăn đôi khi lại tốn thêm tiền taxi. Dù vậy, đôi lúc Grammy vẫn chọn đi ăn ngoài cùng đồng đội để cải thiện bữa ăn.
Khi cuối tháng đến gần, Grammy chỉ còn lại $m$ nhân dân tệ cho chi phí sinh hoạt, và cô cần xoay sở trong $n$ ngày tiếp theo với số tiền này. Vào ngày thứ $i$, cô có hai lựa chọn:
- Ăn ở căng tin, nhận được độ hài lòng $a_i$ và tốn $b_i$ nhân dân tệ.
- Đi ăn ngoài cùng đồng đội, nhận được độ hài lòng $c_i$ và tốn $d_i$ nhân dân tệ.
Vì A và B đi ăn ngoài mỗi ngày nên ngày nào cũng phát sinh tiền taxi. Gọi $e_i$ là tiền taxi vào ngày thứ $i$, cả ba người đã đặt ra quy tắc trả tiền taxi như sau:
- Nếu Grammy không đi ăn ngoài vào ngày thứ $i$, thì có xác suất $\frac{p_i}{100}$ là A sẽ trả tiền taxi, và xác suất $(1 - \frac{p_i}{100})$ là B sẽ trả.
- Nếu Grammy đi ăn ngoài vào ngày thứ $i$, và kể từ lần gần nhất Grammy trả tiền taxi (hoặc kể từ ngày đầu tiên nếu Grammy chưa từng trả tiền taxi), cả A và B mỗi người đều đã trả tiền taxi ít nhất một lần (bất kể lúc đó Grammy có đi ăn ngoài hay không), thì lần này Grammy sẽ trả tiền taxi. Ngược lại, một trong hai đồng đội sẽ trả theo quy tắc phía trên.
Mỗi ngày, Grammy sẽ chọn hành động của mình trước bữa ăn. Cô sẽ biết ai đã trả tiền taxi vào ngày hôm trước, và mục tiêu của cô là tối đa hóa kỳ vọng tổng độ hài lòng, đồng thời đảm bảo tổng chi phí không vượt quá $m$ nhân dân tệ trong trường hợp xấu nhất. Nếu ngày nào cô cũng đưa ra quyết định tối ưu, giá trị kỳ vọng của tổng độ hài lòng là bao nhiêu?
Dữ liệu vào
Mỗi tệp dữ liệu chỉ có duy nhất một bộ dữ liệu.
Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), biểu thị số ngày và giới hạn tổng chi phí.
Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa sáu số nguyên $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ và $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$). Ý nghĩa của chúng đã được mô tả ở trên.
Dữ liệu ra
In ra một dòng chứa một số duy nhất, biểu thị giá trị kỳ vọng lớn nhất của tổng độ hài lòng. Nếu không tồn tại kế hoạch nào đảm bảo tổng chi phí nhỏ hơn hoặc bằng $m$ nhân dân tệ trong trường hợp xấu nhất, hãy in ra $-1$.
Câu trả lời của bạn được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$. Cụ thể, giả sử kết quả của bạn là $a$ và đáp án của ban giám khảo là $b$, kết quả của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Ví dụ
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