Hide

# Best Investing

Geraldine has designed a fantastic investment portfolio that is guaranteed to grow at $r\%$ every year, and she wants to maximize how much she can get out of it. Starting now and for the next $y$ years, she can either deposit money into or withdraw money from her account (but not both) once a year, and after each year the amount in the account grows by $r\%$. Her account stores the dollar amount as a real number.

While she has a good job with flexible hours, Geraldine has bills to pay and she can only work so hard in a given year, so she can only deposit up to $\$ d$per year. She’ll enjoy the money grown from her wise investing, but she has no use for withdrawing more than$\$w$ per year so will never do so.

Given these limits, and given that Geraldine starts with an empty account, what is the maximum net gain that she can earn through her investment?

Note that in the first sample case, Geraldine’s best strategy is to deposit $\$ 1000$at first, which after one year grows by$5\% $to$\$1050$. At the end of the first and only year she withdraws the full $\$ 1050$. Her net gain is the difference between her total withdrawals ($\$1050$) and her total deposits ($\$ 1000$) which in this case is$\$50$.

## Input

Input begins with a line consisting of the four space-separated integers $r$, $y$, $d$, and $w$ as described in the problem statement, satisfying that

\begin{align*} 1 & \leq r, y \leq 100\\ 1 & \leq d, w \leq 10^6. \end{align*}

## Output

Output the maximum net gain that Geraldine can earn with her account. Answers will be accepted up to a relative error of $10^{-6}$ or absolute error of $10^{-2}$, whichever is greater. Specifically, if you submit answer $a$ and the correct answer equals $b$, the judge will accept your solution if $\frac{|a-b|}{b} \leq 10^{-6}$ or $|a-b| \leq 10^{-2}$.

Sample Input 1 Sample Output 1
5 1 1000 2000

50

Sample Input 2 Sample Output 2
100 10 1 1000

1513

Sample Input 3 Sample Output 3
7 100 1 100000

13148.3781193723

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show