文学
题目描述
给定 N 个二元组 S={(a1,b1),…,(aN,bN)},定义
f(S,A,B)=(ai,bi)∈Smax(Aai+Bbi).
选出恰好 R 个二元组组成 T⊆S,使
$$\inf_{A,B\in\mathbb Z_{>0}}\frac{f(T,A,B)}{f(S,A,B)}$$
最大。这里 A,B 均为正整数,所求是下确界,包括只能通过比值趋于边界而逼近的值。
至少一个输入二元组不全为0,因此分母对所有合法 A,B 都为正。
输入格式
第一行两个整数 N,R。
接下来 N 行,每行两个整数 ai,bi。
输出格式
输出一行一个数,表示最大值,四舍五入保留六位小数。
样例
5 1
1 5
2 4
3 3
4 2
5 1
0.600000
数据范围
1≤R≤N≤1000,0≤ai,bi≤109,至少一个二元组不全为0。
30%的数据满足 N≤20,50%的数据满足 N≤50。
参考附件
原题资料(本页约定为准)