Лимит времени 1000/1000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Условие задачи
Вася занимается обслуживанием заказов на доставку пиццы. Все покупатели, которых обслуживает Вася, живут на одной длинной улице. Склад с пиццей находится в самом начале этой улицы. Доставку заказов Вася осуществляет с помощью машины. Машина может ехать со скоростью до V км/ч и в нее можно погрузить не более K коробок пиццы. Вася может загружать коробки с пиццей в свою машину на складе и выгружать из машины возле дома заказчика. Будучи опытным работником, Вася может мгновенно разгонять, останавливать и разворачивать свою машину, а также загружать и выгружать коробки с пиццей.
Сегодня Васе поступило N заказов, которые он должен выполнить. Необходимо определить, за какое наименьшее время Вася сможет выполнить все заказы и вернуться на склад. Вася может доставлять заказы в любом порядке, а также по частям. В момент поступления заказов Вася находится возле склада.
Формат входных данных
Первая строка входного файла содержит целые числа N, K и V (1<= N <= 150000; 1 <= K <= 100; 1 <= V <= 200). В последующих N строках находятся по два целых числа Xi и Si (1 <= Xi <= 5*105; Xi ≠ Xj при i ≠ j; 1 <= Si <= 100) - расстояние в метрах от склада до дома i-го заказчика и количество заказанных им коробок с пиццей.
Формат выходных данных
В выходной файл выведите минимальное время в минутах, за которое Вася сможет выполнить все заказы и вернуться на склад, с точностью до двух знаков после десятичной точки.
Пример
| stdin |
stdout |
2 10 60
1000 5
2000 5
|
4.00 |
1 1 120
500 5
|
2.50 |
Для отправки решений необходимо выполнить вход.
|