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.
Input
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,0ai≤100000)
Output
Output the maximal money he can get.Two decimal places reserved. We promise that the answer is less than 1e15
Sample Input
1 10 0
1.0 1.0
3 13 5
7.0 1.0
1.1 0.6
1.0 0.6
Sample Output
10.00
25.64
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
#define inf 2147480000
struct hammer
{
double val;
double cost;
}map[100010];
double final[100010][2];
int n;
double x,y;
int main(int argc, char *argv[])
{
while(scanf("%d",&n)!=EOF)
{
cin>>x>>y;
for(int i=1;i<=n;i++)
cin>>map[i].cost>>map[i].val;
final[n][0]=map[n].val;
final[n][1]=max(1.0,map[n].val/map[n].cost);
for(int i=n-1;i>=1;i--)
{
final[i][0]=final[i+1][0]+map[i].val*final[i+1][1];
final[i][1]=max(final[i+1][1],final[i][0]/map[i].cost);
}
double ans=x*final[1][1]+y*final[1][0];
printf("%.2lf\n",ans);
}
return 0;
}