Уроки зілляваріння (Potions)
На уроках зілляваріння Рон Уізлі, втім, як і завжди, щось наплутав і його субстанція абсолютно не відповідала параметрам завдання. Після отриманої двійки Рон одержав дуже складне домашнє завдання та звернувся по допомогу до Герміони. Подруга, важко зітхнувши, залишилася з ним на відпрацювання та почала розбиратися в умові. Завдання Рона полягало у тому, щоб створити субстанцію мінімальної густини. Для роботи йому було надано N пляшечок заданого об’єму з відомою масою. Однак у розчин дозволялося добавити рівно К інгредієнтів і, ретельно їх перемішуючи, отримати розчин мінімальної густини.
Формат введення-виведення:
Програма Potions зчитує з клавіатури (стандартного пристрою введення) два цілих числа N та K. Далі задано N пар чисел 1<=K<=N<=105 – маси заданих субстанцій та об’єми пляшечок із субстанціями (всі пляшечки повні). Використовувати дозволяється тільки весь вміст пляшечки.
Програма Potions виводить на екран (стандартний пристрій виведення) єдине дійсне число – мінімальну густину створеної субстанції. Відповідь буде вважатися правильною, якщо її відносна або абсолютна похибка не перевищує 10-4.
Приклад вхідних та вихідних даних
|
Введення |
Виведення |
|
3 2 1 1 10 10 1 2 |
0.666678 |
|
3 2 1 1 2 3 6 27 |
0.250041 |