Антон, як вчитель в школі, організовує дискотеку для дітей. Йому було доручено вибрати музикальний плейлист такий, щоб всі були в захваті від свята. Але в Антона величезна база пісень, а час дискотеки, на жаль, обмежений :(.
А саме, у базі є пісень. Кожну пісню можна схарактеризувати двома цілими числами t_i і r_i — довжина пісні, та її рейтинг. Антон, як меломан, хоче вибрати рівно пісень (тобто, не можна вибрати менше), щоб максимізувати відношення суми рейтингу до суми довжин.
Більш формально, нехай — множина пісень і X \subseteq S, |X|=k — підмножина пісень, яка була вибрана в плейлист. Треба максимізувати \displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i}. Тобто, потрібно знайти суму чисел r_i всіх пісень, які будуть грати на дискотеці, знайти суму чисел t_i всіх пісень, які будуть грати на дискотеці, та поділити перше на друге. Ось це число потрібно максимізувати.
Знайдіть та виведіть максимально можливе відношення.
Перший рядок містить два цілі числа , (1 \le k \le n \le 10^5) — сумарна кількість пісень та кількість пісень, які мають бути вибрані в плейлист.
Другий рядок містить цілих чисел r_i (1 \le r_i \le 10^5).
Третій рядок містить цілих чисел t_i (1 \le t_i \le 10^5).
Виведіть одне число — максимальне відношення.
Ваша відповідь буде вважатися правильною, якщо його абсолютна або відносна похибка не перевищує 10^{-4}.
Формально, нехай ваша відповідь рівна , а відповідь журі рівна . Ваша відповідь буде зарахована, якщо і лише якщо \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}.
Приклад
Приклад 1
У першому прикладі є дві пісні, які й потрібно додати в плейлист. Відповідно, відношення буде таким:
У другому прикладі найкраще взяти третю та п'яту пісню. Відповідно, відношення буде таким: