Mô tả và yêu cầu

Trên tuyến đường một chiều, tình trạng giao thông trở nên đông đúc. Để đảm bảo an
toàn, lực lượng chức năng phân nhóm cho các xe qua cầu. Các xe phải di chuyển
tuần tự theo nhóm (nghĩa là nhóm 𝑖 chỉ được di chuyển sau khi toàn bộ xe của nhóm
𝑖− 1 đã qua cầu và các xe không được phép vượt nhau), tổng trọng lượng của các
xe trong cùng một nhóm không được vượt quá trọng tải của cầu. Thời gian qua cầu
của mỗi nhóm bằng thời gian qua cầu của xe có vận tốc thấp nhất trong nhóm.
Có 𝑛 xe đến cầu, các xe được đánh số thứ tự từ 1 đến 𝑛, xe thứ 𝑖 có vận tốc là 𝑤𝑖
và chạy với vận tốc là 𝑣𝑖. Biết cầu có trọng tải 𝑃, chiều dài 𝐿. Giả thiết rằng 𝑃 ≥
𝑤𝑖∀𝑖 = 1 … 𝑛.
Yêu cầu: Bỏ qua khoảng cách giữa các xe, hãy tìm phương án tách đoàn xe thành
từng nhóm để toàn bộ xe qua cầu được đảm bảo an toàn và tổng thời gian qua cầu
là nhỏ nhất.
Dữ liệu: đọc từ thiết bị nhập chuẩn có dạng:

 Dòng đầu ghi ba số nguyên 𝑛, 𝑃, 𝐿(1 ≤ 𝑛 ≤ 1000,1 ≤ 𝑃 ≤ 100,1 ≤ 𝐿 ≤
1000).
 Dòng thứ 𝑖 trong 𝑛 dòng tiếp theo ghi hai số nguyên là 𝑤𝑖, 𝑣𝑖(1 < 𝑤𝑖 ≤
𝑃, 1 ≤𝑣𝑖 ≤ 100 )

Kết quả: ghi ra thiết bị xuất chuẩn gồm một dòng duy nhất chứa một số thực là
thời gian nhỏ nhất tìm được (làm tròn 2 chữ số thập phân)

Ví dụ

INPUT                    OUTPUT                      Giải thích
 10 100 100               24.33                       - Nhóm 1: Xe 1 - thời gian qua cầu:
 40 25                                                4.00
 50 20                                                - Nhóm 2: Xe 2, 3 - thời gian qua
                                                      cầu: 5.00
 50 20                                                - Nhóm 3: Xe 4, 5, 6 - thời gian
 70 10                                                qua cầu: 10.00
 12 50                                                - Nhóm 4: Xe 7,8- thời gian qua
                                                      cầu: 3.33
 9 70                                                 - Nhóm 5: Xe 9,10 - thời gian qua
 49 30                                                cầu: 2.00

 383 5                                              Tổng thời gian qua cầu:
 27 50                                              4.00+5.00+10.00+3.33+2.00=24.33
 19 70

Giới hạn:
      60% số test đầu tiên 𝑛    ≤  10
      30% số test đầu tiên 𝑛    ≤  100
      10% số test cuối cùng 𝑛     ≤  1000.