zoj 3634 Bounty hunter(dp,已经想明白)

M – Bounty hunter

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status


Bounty hunter is a hero who always moves along cities to earn money by his power. One day he decides to N cities one by one

At the beginning ,Bounty hunter has X money and Y points of Attack force. At day 1, he will goes to city 1, then city 2 at day 2, city 3 at day 3, … At last ,he goes to city N at day N and leaves it at day N+1. In each city, he can increase his attack force by money and earn some money by accepting a task. In the city i, it costs him ai money to increase one point of attack force. And he can gets bi*yi money after finishing the task in city i while yi is his attack force after his increasing at city i.

As it’s known to all that money is the life of Bounty hunter, he wants to own as much money as he can after leaving city N. Please find out the maximal moeny he can get.

PS1: when Bounty hunter leaves a city he won’t come back.

PS2: Bounty hunter can increases his attack force by any real numbers he wants, if the money is enough. For example, if he has 7 money and the unit price of attack force at the city he stays now is 2, he can spend 3 money to increase attack force by 1.5.

PS3: After Bounty hunter finishes the task he will leave the city at once. It means he can and only can increase his attack force before he finishes the task and gets the money at the same city.


The first line of the input is three integers N,X,Y, (0≤N,X,Y≤100000) following is N lines. In the i-th line has two real number ai and bi.(0≤bi≤1,0<ai≤100000)


Output the maximal money he can get.Two decimal places reserved. We promise that the answer is less than 1e15

Sample Input

Sample Output

View Code


Posted in ACM