Дискотека#269

Дискотека

3 секунди
256 мегабайтів
Середня

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

А саме, у базі є пісень. Кожну пісню можна схарактеризувати двома цілими числами 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}.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі є дві пісні, які й потрібно додати в плейлист. Відповідно, відношення буде таким:

\frac{1+2}{2+3}=\frac{3}{5}=0.6

У другому прикладі найкраще взяти третю та п'яту пісню. Відповідно, відношення буде таким:

\frac{3+3}{2+3}=\frac{6}{5}=1.2