Đoàn xe qua cầu

Sau chiến dịch phản gián triệt phá mạng phân cấp gián điệp trên quốc gia mình, không may 009 cũng làm lộ thông tin các mật vụ của minh đang hoạt động trên quốc gia khác. Anh cần nhanh chóng di tản toàn bộ mật vụ về nước bằng một đoàn xe gồm n chiếc theo con đường một chiều và đoàn xe đã được bố trí theo thứ tự từ 1 đến n. Mỗi một xe trong đoàn có vận tốc là v_i và trọng lượng w_i.

Khi đi qua một chiếc cầu có trọng tải giới hạn là P thì đoàn xe phải chia thành các nhóm sao cho tổng trọng lượng của mỗi nhóm không quá P (Lưu ý rằng không được đảo thứ tự đoàn xe). Các nhóm phải đi tuần tự có nghĩa là nhóm thứ i chỉ được khởi hành khi mà toàn bộ xe của nhóm thứ i - 1 đã qua cầu. Giả thiết rằng P > w_i với "i: 1 £ i £ n.

Rõ ràng khi đó thời gian để một nhóm xe qua cầu phụ thuộc vào xe chậm nhất trong nhóm đó nếu coi như chiều dài cũng như khoảng cách của các xe là không đáng kể.

Vì phải di tản qua cầu thật nhanh, 009 cần tìm cách chia đoàn xe thành các nhóm sao cho thời gian mà đoàn xe sang được cầu là nhỏ nhất có thể được.

Dữ liệu: 

·         Dòng đầu là 3 số nguyên dương n, P và L (n, P, L £ 1000) thể hiện cho số xe, trọng lượng giới hạn của cầu và độ dài của cầu.

·         Dòng thứ i trong n dòng kế tiếp gồm 2 số nguyên dương w_i và v_i (w_i, v_i £ 100)

Kết quả: 

·         Ghi một dòng duy nhất chứa một số thực là tổng thời gian nhỏ nhất để đoàn xe qua cầu, kết quả làm tròn lấy 2 chữ số sau dấu chấm thập phân.

Các số trên một dòng của Input / Output  ghi cách nhau ít nhất một dấu cách.

 Ràng buộc:

• Đề không ràng buộc gì thêm

Ví dụ: