Những con kiến đi kiếm ăn hay về tổ thường tổ chức đi theo từng đoàn. Trong một lần nọ, có một đoàn kiến gồm \(n\) con đi trên một nhánh cây và được đánh số thứ tự từ 1 đến \(n\), con kiến thứ \(i\) có vận tốc di chuyển riêng là \(v_{i}\) và khối lượng tương ứng là \(k_{i}\) (với \(i\ = \ 1,\ 2,\ ...,\ n\)). Theo lộ trình thì đoàn kiến sẽ đi tuần tự theo thứ tự để đi kiếm thức ăn. Tuy nhiên trên lộ trình đi có một cành cây không được đảm bảo để cả đoàn kiến di chuyển qua lại một cách thoải mái. Được biết rằng nếu như tổng khối lượng các con kiến cùng trên cành cây đó vượt quá khối lượng \(m\) thì cành cây có thể bị cong hoặc gãy làm cho các con kiến có thể bị rơi xuống đất (tức là trong cùng một thời điểm thì tổng khối lượng các con kiến trên cành cây đó không được vượt quá khối lượng \(m\). Chính vì thế khi đi qua cành cây đó thì các con kiến phải chia đoàn thành các nhóm sao cho tổng khối lượng của mỗi một nhóm là không quá \(m\), các con kiến trong từng nhóm hay các nhóm với nhau cũng phải tuân theo thứ tự ban đầu. Thêm vào đó nữa là các nhóm phải đi tuần tự, nghĩa là nhóm thứ \(i\) chỉ đi được khi mà toàn bộ kiến của nhóm thứ \(i - 1\) đã đi qua được cành cây đó. Vận tốc đi của mỗi một nhóm là hoàn toàn khác nhau và phụ thuộc vào con kiến có tốc độ chậm nhất. Nhiệm vụ của đoàn kiến là phải đi qua cành cây đó càng nhanh càng tốt để thời gian đi kiếm thức ăn không bị quá chậm trễ do cành cây đó gây ra.

Yêu cầu: Hãy sắp xếp đoàn kiến đi sao cho hợp lý để tổng thời gian qua cành cây đó là nhỏ nhất.

Dữ liệu:

+ Dòng đầu là 3 số nguyên dương \(n\), \(m,\ l\); với \(n\) là số lượng kiến của đoàn, \(m\) là tải trọng tối đa của cành cây (tổng khối lượng tối đa của nhóm kiến có thể cùng qua được cành cây) và \(l\) là độ dài của cành cây \((1 \leq \ n\ \leq 1000;\ 1\ \leq \ m,\ l\ \leq 100)\);

+ Trong \(n\) dòng sau, dòng thứ \(i\) là 2 số nguyên dương \(k_{i}\) và \(v_{i}\) thể hiện cho khối lượng và vận tốc của con kiến thứ \(i\) (\(1\ \leq \ k_{i},\ v_{i}\ \leq 100\) với \(i\ = \ 1,\ 2,\ ...,\ n)\).

Kết quả:

+ Ghi thời gian nhỏ nhất để đoàn kiến qua được cành cây (lấy 2 số phần thập phân).

Ví dụ:

Giải thích: Chia thành 3 nhóm: Nhóm 1 (gồm con kiến 1 2, thời gian là 5); Nhóm 2 (gồm con kiến 3, thời gian là 5); Nhóm 3 (gồm con kiến 4 5 6, thời gian là 10). Tổng là: 5 + 5 + 10 = 20.