10264: CF EDU - Binary Search - Step 4 - C. Pair Selection
[Creator : ]
Description
Given $n$ pairs of positive integers $(a_1,b_1),(a_2,b_2),…,(a_n,b_n)$. Select $k\ (1≤k≤n)$ of them $i_1,i_2,…,i_k$ so that the ratio $\frac{a_{i1}+a_{i2}+⋯+a_{ik}}{b_{i1}+b_{i2}+⋯+b_{ik}}$ is maximum possible.
Input
The first line contains integers $n,k\ (1≤k≤n≤10^5)$.
The next $n$ lines contain pairs of integers $a_i,b_i\ (1≤a_i,b_i≤10^5)$.
The next $n$ lines contain pairs of integers $a_i,b_i\ (1≤a_i,b_i≤10^5)$.
Output
Print the required maximum ratio. The answer will be considered correct if the relative or absolute error does not exceed $10^{-6}$.
Sample 1 Input
3 2
10 3
9 5
7 4
Sample 1 Output
2.4285714286
Sample 2 Input
8 3
4 2
4 2
2 2
1 5
5 3
3 5
2 2
5 3
Sample 2 Output
1.8571428571