Quynh has recently launched a new business, and it's thriving. She now wants to plan for her financial freedom. Here are the details:

1. Quynh estimates her income for the next N months as M_i, where i ranges from 0 to N-1.
2. After receiving her monthly profit, Quynh spends X USD on expenses. The monthly expenses increase according to an annual inflation rate of f%.
3. Quynh invests the surplus amount each month with an annual interest rate of r%.
4. Her goal is to accumulate enough money to sustain her lifestyle for the next 100 years (1200 months from starting her work)

Help Quynh calculate the maximum initial amount X_0 (in USD) that Quynh may spend.

Input

• The first line contains three values: N (number of months of work), r% (annual interest rate), and f% (annual inflation rate).
• The second line consists of N space-separated values representing Quynh's monthly salary: M_i for i = 0, 1, ..., N-1.

Output

Print the value of X_0. The result is rounded down in units.

Example

Input

12 5.2 3.6
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000

Output

1952

Input

10 3 2
119879 251746 396800 556359 731874 924940 1137313 1370924 1627895 1910564

Output

11701