Nông dân John mang theo \(N\) con bò, được đánh số từ \(1\) đến \(N\), đến hội chợ quận để tham gia cuộc thi tài năng thường niên dành cho bò! Con bò thứ \(i\) có trọng lượng \(w_i\) và mức tài năng \(t_i\), đều là các số nguyên.

Khi đến nơi, nông dân John khá ngạc nhiên trước luật thi năm nay:

• Một nhóm bò có tổng trọng lượng ít nhất là \(W\) phải được chọn để tham gia cuộc thi (nhằm đảm bảo rằng các nhóm bò mạnh sẽ thi đấu, chứ không chỉ những cá thể mạnh riêng lẻ).
• Nhóm có tỷ lệ tổng tài năng trên tổng trọng lượng cao nhất sẽ chiến thắng.

Nông dân John nhận thấy rằng tổng trọng lượng tất cả bò của mình đều lớn hơn hoặc bằng \(W\), nên chắc chắn có thể chọn được một nhóm hợp lệ. Hãy giúp ông ta xác định tỷ lệ tối ưu giữa tổng tài năng và tổng trọng lượng mà ông có thể đạt được.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) \((1 \leq N \leq 250)\) và \(W\) \((1 \leq W \leq 1000)\).
• \(N\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(w_i\) \((1 \leq w_i \leq 10^6)\) và \(t_i\) \((1 \leq t_i \leq 10^6)\) — trọng lượng và mức tài năng của con bò thứ \(i\).

Dữ liệu ra

• In ra giá trị lớn nhất của tỷ số giữa tổng tài năng và tổng trọng lượng mà nông dân John có thể đạt được khi chọn một nhóm có tổng trọng lượng ít nhất \(W\). Nếu đáp án là \(A\), hãy in ra \(\lfloor 1000 \cdot A \rfloor\) (tức là nhân với 1000 rồi làm tròn xuống).

Input 1

3 15
20 21
10 11
30 31

Output 1

1066

Gợi ý

• Trong ví dụ này, tỷ số tài năng trên trọng lượng tốt nhất là khi chọn bò thứ hai (11/10), nhưng vì cần ít nhất \(15\) đơn vị trọng lượng, nên lời giải tối ưu là chọn bò thứ hai (10, 11) và bò thứ nhất (20, 21). Khi đó tổng tài năng là \(32\) và tổng trọng lượng là \(30\), nên tỷ số là \(32 / 30 = 1.0666...\), nhân với 1000 rồi làm tròn xuống được \(1066\).