[USACO18OPEN] Talent Show G

题目描述

Farmer John 要带着他的 $n$ 头奶牛,方便起见编号为 $1\ldots n$,到农业展览会上去,参加每年的达牛秀!他的第 $i$ 头奶牛重量为 $w_i$,才艺水平为 $t_i$,两者都是整数。 在到达时,Farmer John 就被今年达牛秀的新规则吓到了: (一)参加比赛的一组奶牛必须总重量至少为 $W$(这是为了确保是强大的队伍在比赛,而不仅是强大的某头奶牛),并且。 (二)总才艺值与总重量的比值最大的一组获得胜利。 FJ 注意到他的所有奶牛的总重量不小于 $W$,所以他能够派出符合规则(一)的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

输入输出格式

输入格式


第一行是两个整数,分别表示牛的个数 $n$ 和总重量限制 $W$。 第 $2$ 到 $(n+1)$ 行,每行两个整数,第 $(i + 1)$ 行的整数表示第 $i$ 头奶牛的重量 $w_i$ 和才艺水平 $t_i$。

输出格式


请求出 Farmer 用一组总重量最少为 $W$ 的奶牛最大可能达到的总才艺值与总重量的比值。 如果你的答案是 $A$,输出 $1000A$ 向下取整的值,以使得输出是整数(当问题中的数不是一个整数的时候,向下取整操作在向下舍入到整数的时候去除所有小数部分)。 请注意当问题的答案恰好是整数 $x$ 时,你的程序可能会由于**浮点数精度误差**问题最后得到一个 $x-\epsilon$ 的答案,向下取整后变为 $x-1$ 导致答案错误。这种情况下你可以在输出答案前给答案加上一个极小的值 $x\gets x+10^{-k}$ 来避免该问题。

输入输出样例

输入样例 #1

3 15
20 21
10 11
30 31

输出样例 #1

1066

说明

#### 样例解释 在这个例子中,总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为 $11$、重量为 $10$ 的奶牛,但是由于我们需要至少 $15$ 单位的重量,最优解最终为使用这头奶牛加上才艺值为 $21$、重量为 $20$ 的奶牛。这样的话才艺与重量的比值为 $\frac{11+21}{10+20}=\frac{32}{30} = 1.0666\dots$,乘以 $1000$ 向下取整之后得到 $1066$。 #### 数据规模与约定 对于全部的测试点,保证 $1 \leq n \leq 250$,$1 \leq W \leq 1000$,$1 \leq w_i \leq 10^6$,$1 \leq t_i \leq 10^3$。