Talent Show

题目描述

Farmer John 要带着他的 $N$ 头奶牛（方便起见编号为 $1 \ldots N$）去参加县集市，参加一年一度的奶牛才艺秀！第 $i$ 头奶牛的体重为 $w_i$，才艺值为 $t_i$，两者都是整数。

到达后，Farmer John 对今年才艺秀的新规则感到十分惊讶： (i) 参赛必须提交一组奶牛，且这组奶牛的总重量至少为 $W$（为了确保参赛的是强大的奶牛团队，而不仅仅是强的个体），并且 (ii) 总才艺与总重量之比最大的那一组将获胜。

FJ 注意到他所有奶牛的总重量至少为 $W$，因此他应该能够提交一支满足 (i) 的队伍。请帮助他确定在满足条件的队伍中，他能达到的最优才艺/重量比值。

输入格式

第一行输入 $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$ 的一组奶牛中，Farmer John 能达到的最大“总才艺/总重量”比值。若答案为 $A$，请输出 $\lfloor 1000A \rfloor$，以保证输出为整数（向下取整会丢弃小数部分；若该数本身为整数则不变）。

3 15
20 21
10 11
30 31

1066

提示

在该例中，整体上最好的才艺/重量比会是只选那头才艺 11、体重 10 的奶牛，但由于总重量至少需要 15，因此最优解是选这头奶牛再加上那头才艺 21、体重 20 的奶牛。这样得到的才艺/重量比为 (11+21)/(10+20) = 32/30 = 1.0666666...，乘以 1000 并向下取整得到 1066。 题目来源：Brian Dean

标签: USACO|2018|Gold

来源

USACO|2018|Gold