Антон, як вчитель в школі, організовує дискотеку для дітей. Йому було доручено вибрати музикальний плейлист такий, щоб всі були в захваті від свята. Але в Антона величезна база пісень, а час дискотеки, на жаль, обмежений :(.
А саме, у базі є $$$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$$$$$$