Time limit 1000/1000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Problem description
Bob is pizza delivery guy. He has a car and all his clients live on a same long street. Pizza stock is right at the begining of the street. His car can travel at speed V km/h and it can't be loaded with more then K boxes of pizza. He is so professional that it doesn't take him any time to load and unload car with boxes, he can instantly accelerate to maximum speed, stop and deploy his car.
Today Bob received N orders. Find the minimum time which is needed to deliver all pizzas and get back to stock. At the beginning he is at the stock.
Input
There are three integers on the first line of input N, K and V (1<= N <= 150000; 1 <= K <= 100; 1 <= V <= 200). On every next N lines there are two integers Xi and Si (1 <= Xi <= 5*105; Xi ≠ Xj if i ≠ j; 1 <= Si <= 100) - distance in meters from stock to the i-th clients house and number of boxes of pizza he ordered.
Output
Write the minimum time in minutes (with 2 digits after the point) which is needed to deliver all pizzas and turn back to stock.
Example
| stdin |
stdout |
2 10 60
1000 5
2000 5
|
4.00 |
1 1 120
500 5
|
2.50 |
Для отправки решений необходимо выполнить вход.
|