#2408. 「THUPC 2017」组合数问题 / Problem

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: yuzhihang

题目描述

小葱是一名勇士。

小葱踏上了拯救世界的征途。

小葱面前有 N 只大葱怪。

大葱怪很厉害,第 i 只大葱怪攻击力为 a_i ,防御力为 d_i

小葱的攻击力为 A ,防御力为 D

小葱打掉第 i 只大葱怪的代价是 A\cdot d_i+D\cdot a_i

小葱打倒很多只大葱怪的代价不是打倒每一只大葱怪的代价之和,而是最大值。

小葱现在需要打倒 R 只大葱怪。

神葱是葱的神,神葱会对小葱打倒 R 只大葱怪做出评价。神葱对小葱打倒 R 只大葱的评价为小葱打倒这 R 只大葱怪所需要的代价除以小葱以同样的攻击力和防御力打倒所有 N 只大葱怪的代价。

神葱是葱的神,所以神葱会在小葱选择了 R 只要被打倒的大葱怪后,设定小葱的攻击力和防御力,使得小葱得到的评价最低。

神葱不希望这个值是负的,所以如果这个值是负的,神葱会强制把它变为 0

小葱是一名勇士。

小葱不会屈服。

小葱需要选择出 R 只大葱怪,使得自己能够从神葱那里得到的评价最高。

小葱求这个评价值。

小葱很善良,所以小葱为你写出了评价值的数学表示:

\max_{S\subseteq[N],|S|=R}\left[\min_{A,D\in\mathbb{Z}^+}\frac{\max_{i\in R}\left(A\cdot d_i+D\cdot a_i\right)}{\max_{i\in[N]}\left(A\cdot d_i+D\cdot a_i\right)}\right]

输入格式

测试点包含多组数据。

对于每组数据,第一行两个整数代表 N,R

接下来 N 行每行两个实数分别代表 a_i,d_i

输出格式

对于每组数据,一行一个实数代表答案,你需要保证你的答案与标准答案的误差不超过 10^{-6}

样例

样例输入

3 3
1 3
2 5
2 3
5 1
1 5
2 4
3 3
4 2
5 1

样例输出

1.000000
0.600000

数据范围与提示

1\leq R\leq N\leq 10^3 a_i,d_i 均为正整数,数据组数不超过 50 组,所有攻击力和防御力都是正整数。