Farmer John đưa $N$ bò đánh số $1\ldots N$ đến hội chợ hạt dự thi tài năng bò hằng năm. Bò $i$ có cân nặng nguyên $w_i$ và tài năng nguyên $t_i$.

Luật mới làm ông bất ngờ:

(i) Nhóm phải nặng ít nhất $W$, để đội mạnh chứ không chỉ cá thể mạnh thi đấu.

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

Tổng cân nặng của tất cả bò ít nhất $W$ nên thỏa (i) được. Tìm tỉ lệ lớn nhất cho đội như vậy.

Dữ liệu vào

Dòng đầu chứa $N$ ($1 \leq N \leq 250$), $W$ ($1 \leq W \leq 1000$). $N$ dòng sau cho các số nguyên $w_i$ ($1 \leq w_i \leq 10^6$), $t_i$ ($1 \leq t_i \leq 10^3$).

Dữ liệu ra

Tìm tỉ lệ lớn nhất khi cân nặng ít nhất $W$. Nếu là $A$, in sàn của $1000A$ để cho số nguyên; sàn bỏ phần lẻ và làm tròn xuống nếu chưa nguyên.

Ví dụ

Dữ liệu vào 1

3 15
20 21
10 11
30 31

Dữ liệu ra 1

1066

Ghi chú

Tài năng 11, cân nặng 10 là tốt nhất riêng lẻ, nhưng cần 15 nên chọn thêm tài năng 21, cân nặng 20. $(11+21)/(10+20)=32/30=1.0666666...$, nhân 1000 làm tròn xuống, cho 1066.

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