Description

Farmer John 要带着他的 n 头奶牛，方便起见编号为 1…n，到农业展览会上去，参加每年的达牛秀！他的第 i 头奶牛重量为 wi，才艺水平为 ti，两者都是整数。

在到达时，Farmer John 就被今年达牛秀的新规则吓到了：

①参加比赛的一组奶牛必须总重量至少为 W（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛）。

②总才艺值与总重量的比值最大的一组获得胜利。

FJ 注意到他的所有奶牛的总重量不小于 W，所以他能够派出符合规则①的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

Format

Input

第一行是两个整数，分别表示牛的个数 n 和总重量限制 W。

第 2 到 (n+1)行，每行两个整数，第(i+1) 行的整数表示第 i 头奶牛的重量 wi 和才艺水平 ti。

Output

请求出 Farmer 用一组总重量最少为 W 的奶牛最大可能达到的总才艺值与总重量的比值。如果你的答案是 A，输出 1000*A 向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

Samples

20 21 
10 11 
30 31

1066

样例解释

数据说明

对于 70%的测试点：保证 1≤n≤250，1≤W≤1000，1≤wi , ti≤10^3。

对于全部的测试点，保证 1≤n≤250，1≤W≤1000，1≤wi≤10^6，1≤ti≤10^3。