P1570 KC Drinks Coffee

KC and SH often went to 85°C in Fuzhou to drink coffee or something else. One day, KC wanted a cup of coffee. The waiter told him there are $n$ kinds of seasonings, and exactly $m$ of them can be added to this cup of coffee (KC will add exactly $m$ kinds, not fewer). Depending on which seasonings are added, the time needed to make the coffee and the resulting deliciousness will differ. After learning all $n$ seasonings, as a former chemistry contest ace, KC immediately knows the time cost $c _ i$ and the deliciousness $v _ i$ of each seasoning. Since KC is in a hurry to get back to solving problems, he wants to drink the coffee as soon as possible, but he also wants it to be delicious. So he came up with a plan: he wants to drink the coffee that maximizes $\dfrac{\sum v _ i}{\sum c _ i}$, that is, the deliciousness per unit time. Now KC tells SH the information about the seasonings and asks SH to compute the $\dfrac{\sum v _ i}{\sum c _ i}$ of the coffee he will drink. But SH does not want to help, so KC turns to you. Note: $\sum$ denotes summation, so $\dfrac{\sum v _ i}{\sum c _ i}$ means the total deliciousness divided by the total time cost.

The input consists of three lines. - The first line contains two integers $n, m$, the number of seasonings and the number to add. - The next two lines each contain $n$ integers. In these two lines, the $i$-th integer of the first line is the deliciousness $v _ i$ of seasoning $i$, and the $i$-th integer of the second line is the time cost $c _ i$ of seasoning $i$.

Output a real number $T$, the maximum value of $\dfrac{\sum v _ i}{\sum c _ i}$ for KC’s coffee, rounded to three decimal places.

Explanation for Sample 1: KC chooses seasonings $2$ and $3$, $\dfrac{\sum v _ i}{\sum c _ i} = \dfrac{2 + 3}{2 + 1} = 1.667$. It can be verified that there is no better choice. Constraints: For $20 \%$ of the testdata: $1 \leq n \leq 5$. For $50 \%$ of the testdata: $1 \leq n \leq 10$. For $80 \%$ of the testdata: $1 \leq n \leq 50$. For $100 \%$ of the testdata: $1 \leq n \leq 200, 1 \leq m \leq n, 1 \leq c[i], v[i] \leq 1 \times 10 ^ 4$. The testdata guarantees that the answer does not exceed $1000$. Translated by ChatGPT 5