Tốc độ tối thượng

Bạn đang chơi một trò chơi gồm $N$ màn, phải hoàn thành lần lượt theo thứ tự từ màn $1$ đến màn $N$. Với mỗi màn $i$:

• Có xác suất $P_i\%$ hoàn thành trong $F_i$ giây (đi nhanh).
• Có xác suất $(100-P_i)\%$ hoàn thành trong $S_i$ giây (đi chậm), với $F_i<S_i$.

Sau khi hoàn thành một màn, bạn được phép chọn tiếp tục sang màn tiếp theo, hoặc reset trò chơi và chơi lại từ màn $1$. Cả hai hành động này đều diễn ra tức thì (không tốn thêm thời gian).

Mục tiêu: hoàn thành cả $N$ màn liên tiếp với tổng thời gian không vượt quá $R$ giây. Hỏi với chiến lược tối ưu, kỳ vọng tổng thời gian phải chơi cho đến khi đạt được mục tiêu là bao nhiêu?

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $R$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $F_i$, $S_i$, $P_i$.

Dữ liệu ra

In ra một số thực — kỳ vọng tổng thời gian chơi. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le N\le 50$.
• $1\le R\le 5000$.
• $1\le F_i<S_i\le 100$.
• $80\le P_i\le 99$.

Ví dụ