Thời gian đoàn xe qua cầu

Người ta muốn xây dựng một khu du lịch trên một quần đảo xinh đẹp. Giữa đảo và đất liền chỉ có một chiếc cầu cho phép giao thông một chiều. Cầu có trọng tải tối đa là \(P\) và chiều dài là \(L\). Một đoàn xe gồm \(N\) chiếc được đánh số từ \(1\) đến \(N\) đang vận chuyển vật liệu từ đất liền ra đảo, xe thứ \(i\) có tổng trọng lượng là \(w_i\), chạy với vận tốc là \(v_i\). Để đảm bảo thời gian vận chuyển vật liệu và tải trọng của cầu, cơ quan chức năng chỉ cho phép từng nhóm xe tuần tự qua cầu. Nhóm xe sau chỉ được di chuyển sau khi toàn bộ xe của nhóm trước đã qua cầu, các xe không được phép vượt nhau và tổng trọng lượng các xe trong một nhóm không được vượt quá tải trọng của cầu. Thời gian qua cầu của mỗi nhóm phụ thuộc vào xe có vận tốc thấp nhất trong nhóm, cụ thể bằng \(L\) chia cho vận tốc nhỏ nhất đó.

Do các xe không được vượt nhau nên mỗi nhóm gồm các xe có số thứ tự liên tiếp nhau.

Yêu cầu: Hãy tìm phương án chia \(N\) xe thành từng nhóm để tổng thời gian di chuyển qua cầu của cả đoàn xe là nhỏ nhất.

Input

Dữ liệu vào gồm:

• Dòng thứ nhất ghi ba số nguyên \(N, P, L\) (\(1 \le N \le 1000\), \(1 \le P \le 100\), \(1 \le L \le 1000\));

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi hai số nguyên \(w_i, v_i\) (\(1 \le w_i \le P\), \(1 \le v_i \le 100\)) là tổng trọng lượng và vận tốc của xe thứ \(i\).

Ràng buộc:

• Có \(60\%\) số test thỏa mãn \(N \le 10\);

• Có \(30\%\) số test thỏa mãn \(N \le 100\);

• Có \(10\%\) số test thỏa mãn \(N \le 1000\).

Output

In ra một số thực duy nhất là thời gian nhỏ nhất tìm được (chính xác đến \(2\) chữ số thập phân).

Example

Input:

7 80 100
40 25
30 20
50 20
60 10
10 50
9 70
49 30

Output:

22.33

Note

Một cách chia tối ưu:

• Nhóm 1 gồm xe 1; thời gian: \(100/25 = 4.00\);

• Nhóm 2 gồm xe 2, 3 (tổng trọng lượng \(80\)); thời gian: \(100/20 = 5.00\);

• Nhóm 3 gồm xe 4, 5, 6 (tổng trọng lượng \(79\)); thời gian: \(100/10 = 10.00\);

• Nhóm 4 gồm xe 7; thời gian: \(100/30 = 3.33\).
  Tổng thời gian qua cầu là \(4.00 + 5.00 + 10.00 + 3.33 = 22.33\).