ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

8091: Talent Show

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：12 通过：10
提交提交记录统计Web Board

题目描述

Farmer John is bringing his NN cows, conveniently numbered 1…N1…N, to the county fair, to compete in the annual bovine talent show! His iith cow has a weight wiwi and talent level titi, both integers.

Upon arrival, Farmer John is quite surprised by the new rules for this year's talent show:

(i) A group of cows of total weight at least WW must be entered into the show (in order to ensure strong teams of cows are competing, not just strong individuals), and

(ii) The group with the largest ratio of total talent to total weight shall win.

FJ observes that all of his cows together have weight at least WW, so he should be able to enter a team satisfying (i). Help him determine the optimal ratio of talent to weight he can achieve for any such team.

INPUT FORMAT (file talent.in):

The first line of input contains NN (1≤N≤2501≤N≤250) and WW (1≤W≤10001≤W≤1000). The next NN lines each describe a cow using two integers wiwi (1≤wi≤1061≤wi≤106) and titi (1≤ti≤1031≤ti≤103).

OUTPUT FORMAT (file talent.out):

Please determine the largest possible ratio of total talent over total weight Farmer John can achieve using a group of cows of total weight at least WW. If your answer is AA, please print out the floor of 1000A1000A in order to keep the output integer-valued (the floor operation discards any fractional part by rounding down to an integer, if the number in question is not already an integer).

SAMPLE INPUT: 

3 15
20 21
10 11
30 31

SAMPLE OUTPUT: 

1066

In this example, the best talent-to-weight ratio overall would be to use just the single cow with talent 11 and weight 10, but since we need at least 15 units of weight, the optimal solution ends up being to use this cow plus the cow with talent 21 and weight 20. This gives a talent-to-weight ratio of (11+21)/(10+20) = 32/30 = 1.0666666..., which when multiplied by 1000 and floored gives 1066.

输入样例 复制 

3 15
20 21
10 11
30 31

输出样例 复制 

1066

分类标签