High School Programming League Problems Archive

For his twelfth birthday, Johnny intends to invite his friends to the blockbuster movie "Enroll in SPOJ!". However, since tickets may be purchased only one day in advance, he is not at all sure whether he will manage to get some seats. So, as an emergency alternative, he is planning to organize a "garden party" with plenty of sweets. The prices of sweets change every day, and Johnny would have to buy them a day before the party, so his a bit worried the price might be a bit high on that day. So, Johnny goes to his local shop and offers the following deal to old shopkeeper Leo:

"I would like to have the option of buying, in one month's time, a fixed number of sweets for the price we agree on today. I know that the prices change every day and it can happen that the market price on the day of transaction will be different from the price we decide on today. I can't even promise that I will buy the sweets because I might go the cinema instead. So, will you sell me the option of buying the sweets in a month's time, at the price agreed on today, and if so, for how much?"

Leo thought it over and said: "So, I am obliged to sell you the sweets, if you wish to buy them, and you may buy the sweets, but you do not have to? Well, I agree, but this will cost you!" - and Leo gave a hefty sum.

Johnny has to think over whether the offer made by Leo is fair, taking into account the fluctuations of prices, and the exact terms of the deal. Help Johnny calculate the fair price of the sweet option!

Formally, Johnny and Leo have settled a strike price on the expiration day in T days from now (0 < T < 50) equal to X (0 < X < 1000). The starting price (i.e. today's price) of the sweets is equal to S₀ (0 < S₀ < 100). Every day the price changes: it rises to the value u·S (1 < u < 1.6) with a probability of p (0 < p < 1) or falls to d·S (0 < d < 1) with probability 1-p, where S is the previous day's price. Since Johnny has the right, but not the obligation, to buy sweets, his profit is equal to max{S_T - X,0}, where S_T is the official price of sweets on the expiration day, exactly in T days time. Taking into account the potential profit made by Johnny, Leo has to make up for his own potential loss, so he wants Johnny to pay some sum C for the sweet option.

By the fair price of the sweet option we mean a value of C equal to the expected value of the profit made by Johnny in T days' time, regarding all potential changes of the prices. We assume that the bank interest rate is equal to 0.

Example: Johnny and Leo have agreed that Johnny can buy sweets tomorrow for 82 PLN (this is X). Today, the price is 80 PLN (S₀). The price can change in one day in accordance with the rules: it can rise to 120 PLN (u=1.5) with probability 1/2 (p) or fall to 60 PLN (d=0.75) with probability 1/2 (1-p). The fair price C of the option in this case is 19 PLN.

Input

Every data set consists of six numbers given in two lines:

T X S0
p u d

The numbers p, u and d are in fixed point format with two digit precision. All other numbers are positive integers.

Output

Write the fair price C of the sweet option with two digits' precision.

Example 1

Input:
1 82 80
0.50 1.50 0.75

Output:
19.00

Example 2

Input:
2 9 10
0.80 1.25 0.75

Output:
4.36

Scoring

For every test data you can get 1, 2 or 3 points, summing to a total of 10 points.