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 的奶牛能得到最高比值，但重量至少要 15，所以还要选才艺 21、重量 20 的奶牛。比值为 $(11+21)/(10+20)=32/30=1.0666666...$，乘 1000 后向下取整得到 1066。

题目作者：Brian Dean