Andy wants to buy a house and can save X amount each month. He will save monthly with interest until he has enough for a 30% down payment of the current house price. Once he has the down payment, he buys the house by taking a loan for the remaining amount and uses the same monthly amount X to repay the loan.

The entire process must be completed within exactly N months from the start.

The initial house price is P0, and it increases at a monthly rate of fi. The value of fi changes every 5 years.

Andy's monthly savings earn interest at rate ri, which also changes every 5 years.

The loan has a fixed monthly interest rate of c.

Given the parameters N, P0, c, and 8 values each for fi and ri, calculate the minimum monthly amount X.

Input

First line: Three values N, P0, and c

• N: Total number of months (integer, N ≤ 480)
• P0: Initial house price in VND (long integer)
• c: Monthly government subsidy interest rate (decimal)

Second line: 8 decimal numbers representing the monthly house price increase rates fi

Third line: 8 decimal numbers representing the monthly savings interest rates ri

Output

A single integer X, representing the minimum monthly amount Andy needs (rounded to the nearest integer).

Example

Input

240 2800000000 0.0042
0.0065 0.0058 0.0051 0.0047 0.0043 0.0041 0.0039 0.0037
0.0045 0.0041 0.0038 0.0037 0.0035 0.0034 0.0033 0.0032

Output

20630021