[USACO18OPEN]Talent Show

题目描述

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

输入输出格式

输入格式


输入的第一行包含$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$)描述了一头奶牛。

输出格式


请求出Farmer用一组总重量最少为$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