Дискотека
ліміт часу на тест
3 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Антон, як вчитель в школі, організовує дискотеку для дітей. Йому було доручено вибрати музикальний плейлист такий, щоб всі були в захваті від свята. Але в Антона величезна база пісень, а час дискотеки, на жаль, обмежений :(.

А саме, у базі є $$$n$$$ пісень. Кожну пісню можна схарактеризувати двома цілими числами $$$t_i$$$ і $$$r_i$$$ — довжина пісні, та її рейтинг. Антон, як меломан, хоче вибрати рівно $$$k$$$ пісень (тобто, не можна вибрати менше), щоб максимізувати відношення суми рейтингу до суми довжин.

Більш формально, нехай $$$S$$$ — множина пісень і $$$X \subseteq S$$$, $$$|X|=k$$$ — підмножина пісень, яка була вибрана в плейлист. Треба максимізувати $$$\displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i}$$$. Тобто, потрібно знайти суму чисел $$$r_i$$$ всіх пісень, які будуть грати на дискотеці, знайти суму чисел $$$t_i$$$ всіх пісень, які будуть грати на дискотеці, та поділити перше на друге. Ось це число потрібно максимізувати.

Знайдіть та виведіть максимально можливе відношення.

Вхідні дані

Перший рядок містить два цілі числа $$$n$$$, $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — сумарна кількість пісень та кількість пісень, які мають бути вибрані в плейлист.

Другий рядок містить $$$n$$$ цілих чисел $$$r_i$$$ ($$$1 \le r_i \le 10^5$$$).

Третій рядок містить $$$n$$$ цілих чисел $$$t_i$$$ ($$$1 \le t_i \le 10^5$$$).

Вихідні дані

Виведіть одне число — максимальне відношення.

Ваша відповідь буде вважатися правильною, якщо його абсолютна або відносна похибка не перевищує $$$10^{-4}$$$.

Формально, нехай ваша відповідь рівна $$$a$$$, а відповідь журі рівна $$$b$$$. Ваша відповідь буде зарахована, якщо і лише якщо $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

Приклади

Вхідні дані

    2 21 22 3

Вихідні дані

    0.600000

Вхідні дані

    5 21 2 3 2 32 4 2 5 3

Вихідні дані

    1.200000

Пояснення

У першому прикладі є дві пісні, які й потрібно додати в плейлист. Відповідно, відношення буде таким: $$$$$$\frac{1+2}{2+3}=\frac{3}{5}=0.6$$$$$$

У другому прикладі найкраще взяти третю та п'яту пісню. Відповідно, відношення буде таким: $$$$$$\frac{3+3}{2+3}=\frac{6}{5}=1.2$$$$$$