2928. [USACO Open18 Gold] Talent Show

【题目描述】

Farmer John要带着他的$N$头奶牛，方便起见编号为$1…N$，到农业展览会上去，参加每年的达牛秀！他的第$i$头奶牛重量为$w_i$，才艺水平为$t_i$，两者都是整数。在到达时，Farmer John就被今年达牛秀的新规则吓到了：

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

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

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

【输入格式】

输入的第一行包含$N$（$1≤N≤250$）和WW（$1≤W≤1000$）。下面$N$行，每行用两个整数$w_i$（$1≤w_i≤10^6$）和$t_i$（$1≤t_i≤10^3$）描述了一头奶牛。

【输出格式】

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

【输入样例】

3 15
20 21
10 11
30 31

【输出样例】

1066

【数据规模】

30%的数据N<=30;

100%的数据N<=250;

【提示】

在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛，但是由于我们需要至少15单位的重量，最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值为(11+21)/(10+20) = 32/30 = 1.0666666...，乘以1000向下取整之后得到1066。

【来源】

USACO 2018 OPEN CONTEST Gold Problem 3

供题：Brian Dean