Bác nông dân John đưa \(N\) cô bò, được đánh số thuận tiện từ \(1 \ldots N\), đến hội chợ của hạt để tham gia cuộc thi tài năng bò thường niên! Cô bò thứ \(i\) có cân nặng \(w_i\) và mức tài năng \(t_i\), đều là các số nguyên.

Khi đến nơi, bác nông dân John khá bất ngờ trước các quy tắc mới của cuộc thi tài năng năm nay:

(i) Phải đưa vào cuộc thi một nhóm bò có tổng cân nặng ít nhất \(W\) (để bảo đảm rằng các đội bò mạnh tham gia tranh tài, chứ không chỉ những cá thể mạnh).

(ii) Nhóm có tỷ lệ tổng tài năng trên tổng cân nặng lớn nhất sẽ chiến thắng.

Bác nông dân John nhận thấy tổng cân nặng của tất cả các cô bò ít nhất là \(W\), nên ông có thể đưa vào thi một đội thỏa mãn điều kiện thứ nhất. Hãy giúp ông xác định tỷ lệ tài năng trên cân nặng tối ưu có thể đạt được với một đội như vậy.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 250\)) và \(W\) (\(1 \leq W \leq 1000\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một cô bò bằng hai số nguyên \(w_i\) (\(1 \leq w_i \leq 10^6\)) và \(t_i\) (\(1 \leq t_i \leq 10^3\)).

Dữ liệu ra

Hãy xác định tỷ lệ lớn nhất có thể giữa tổng tài năng và tổng cân nặng mà bác nông dân John có thể đạt được bằng cách chọn một nhóm bò có tổng cân nặng ít nhất \(W\). Nếu đáp án là \(A\), hãy in \(\lfloor 1000A \rfloor\) để kết quả là một số nguyên. Phép lấy phần nguyên loại bỏ phần thập phân bằng cách làm tròn xuống tới một số nguyên nếu số đang xét chưa phải là số nguyên.

Ví dụ

3 15
20 21
10 11
30 31

1066

Nguồn

USACO 2018 US Open Contest, Gold — Talent Show

Tác giả bài toán: Brian Dean.