Quynh kept working for M months, then took M months unpaid leave to travel for vacation.

Let's calculate Quynh's savings after M months of unpaid travel, knowing that:

1. Quynh's salary of M months as Mi, where i ranges from 0 to M-1.
2. After receiving her monthly salary, Quynh spends X USD on expenses. The monthly expenses increase according to an annual inflation rate of f% which is estimated by: X[i+1] = X[i]*(1+f%/12)
3. Quynh invests the surplus amount each month with an annual interest rate of r% which can be calculated using the formula: SaveMoney[i+1] = SaveMoney[i]*(1+r%/12).

Input

• The number of months M (M ≤ 500), the amount of money earning per each month Mi USD as i = {1,...,M} (Mi ≤ 10^9), the monthly expenditure X USD (X ≤ 10^9), the yearly interest rate r%, the yearly inflation rate f%.

Output

• The amount of saving money remains after M months to traveling. If saving money is negative return 0. The result is rounded to unit.

Example

Input

6
8000 9000 10000 10000 11111 15000
5000
10
10

Output

1827