Farmer John は $1\ldots N$ と番号付けした $N$ 頭の牛を郡の市の年次才芸ショーに連れていきます。牛 $i$ の体重 $w_i$ と才芸 $t_i$ は整数です。

今年の新ルールに驚きました。

(i) 合計体重が $W$ 以上のチームを出します。優れた個体だけでなく、強いチームを競わせるためです。

(ii) 合計才芸と合計体重の比が最大のチームが勝ちます。

全牛の体重は $W$ 以上なので (i) を満たせます。そのようなチームの比の最大値を求めてください。

入力

1 行目に $N$（$1 \leq N \leq 250$）と $W$（$1 \leq W \leq 1000$）。続く $N$ 行には各牛の整数 $w_i$（$1 \leq w_i \leq 10^6$）と $t_i$（$1 \leq t_i \leq 10^3$）。

出力

合計体重 $W$ 以上のチームの最大比を求めます。答えが $A$ なら $1000A$ の床を出力し、整数にします。床は整数でない数の小数部を捨てて整数へ切り下げます。

入出力例

入力 1

3 15
20 21
10 11
30 31

出力 1

1066

注記

才芸 11、体重 10 の 1 頭が最高比ですが、体重 15 以上が必要なので才芸 21、体重 20 の牛も選びます。$(11+21)/(10+20)=32/30=1.0666666...$ を 1000 倍して切り下げると 1066 です。

問題作成：Brian Dean