URI Online Judge | 2713

The Wizard is Relentless

By Diego Rangel, FACIT BR Brazil

Timelimit: 1

In RPG games there are many classes of characters that the players can choose when they start the game. One of the most popular classes is the wizard, because he is relentless! The wizard is the kind of character that dominates mystical arts and therefore causes a constant damage V that varies from match to match, and sometimes, in case he has mana (magic points), he increase his damage to a certain level that depends on the monster he is fighting against.

Rangel is playing a new RPG and he is trying to level up fast, so in order to do that, he needs to play a lot! However, he does not have much time, he has a lot of books he borrowed from his friend Vânia he needs to read and it is exams week, so he needs to study to pass. Therefore, he wants to minimize the amount of time he spends on the game. No rush, we will explain how it works!

First, this RPG works following these procedures: there are several matches, and each one contains N rooms, and in each room there is a monster with X life points. For each monster, in case the wizard has mana, he can increase the value of the constant damage in Di units, and the cost to increase the damage is fixed in 1 mana unit. The time needed to kill an i-th monster is the the amount of life points the monster has divided by the damage the wizard can cause (considering the rules mentioned previously).

It is important to remember that in order to win the match you need to get to the end of it. It is always guaranteed that Rangel plays until the end of the match, and he can only go to the next room when he kills the guardian monster of the room in which he is.

Input

There are several case tests. Each case starts with three integers N, K, V, where (1 ≤ N ≤ 103) indicates the number of rooms there are in the match, K (0 ≤ K ≤ 100) indicates the amount of mana (magic points) the powerful wizard possess and V (1 ≤ V ≤ 104) indicates the value of the constant damage the wizard suffers on this level. The next N lines contain two integers X (1 ≤ X ≤ 105) indicating the number of life points the monster has in the i-th room and Di (1 ≤ Di ≤ 105) indicates how much damage will be increased on the i-th room, in case the wizard has mana and wants to use it.

Output

For each case, you will have to print a line containing the minimum time Rangel will spend to kill all the monsters in the game with four decimal places.

Input Sample Output Sample

5 0 1

1 1

2 1

1 1

1 1

1 1

5 2 1

1 1

2 1

1 1

1 1

1 1

5 2 3

3 5

2 1

7 2

3 1

8 4

6.0000

4.5000

5.2095