EduBrick
← вернуться к уроку · Жадные идеи и их ловушки

Делимый груз

5000 мс · 256 МБ · всё или ничего

Есть nn видов груза: груз вида ii весит wiw_i и стоит cic_i. Груз сыпучий, поэтому от каждого вида можно взять любую часть — стоимость меняется пропорционально.

В машину помещается WW килограммов. Какую наибольшую стоимость можно увезти? Ответ выведите с точностью не хуже 10610^{-6}.

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и WW от 00 до 101210^{12}. Во второй — 2n2n чисел: пары wiw_i и cic_i подряд, оба от 11 до 10610^6.

Формат вывода

Одно вещественное число.

Примеры

ввод
3 50
10 60 20 100 30 120
вывод
240.000000000

Примечание

Выгодность вида груза — это стоимость килограмма. Берём подряд самые выгодные, последний, скорее всего, придётся взять частично.

Войдите, чтобы отправлять решения.
← Вернуться к уроку