Collecting - MarisaOJ: Marisa Online Judge

Collecting

Time limit: 2000 ms
Memory limit: 256 MB
Marisa loves collecting stuff. In front of her, there are $n$ items, where the $i$-th item has a weight of $w_i$ and a value of $v_i$. She wants to take all of them home, but they are too heavy. Therefore, she decides to only take $k$ items. If she takes $k$ items, the value of these items is given by: $$\frac{v_1+v_2+...+v_k}{w_1+w_2+...+w_k}$$ Help Marisa choose items so that the achieved value is maximized. ### Input - The first line contains two integers $n,k$. - The next $n$ lines, each line contains two integers $v_i$ and $w_i$. ### Output - Print a real number, the maximum achievable value. The answer is considered correct if the difference from the correct answer is not greater than $10^{-3}$. ### Constraints - $1 \le k \le n \le 10^5$. - $1 \le v_i, w_i \le 10^9$. ### Example Input: ``` 5 3 1 3 2 2 2 5 4 2 1 4 ``` Output: ``` 1.0000000000 ```