Nicole is a retired wealthy businesswoman who is interested in donating to her favorite charity while maintaining the maximum wealth possible. She currently has $X$ dollars in the bank and would like to donate $Y$ dollars to the charity each year over the next $N$ years. The amount donated in any particular year does not need to be exactly $Y$ dollars, but for any $1 \leq i \leq N$, the total sum donated in the first $i$ years must be at least $i \cdot Y$ dollars.

At the start of each of the $N$ years, Nicole can donate any amount of money to the charity, or none at all. Donations cannot be made at any other time of the year. If she donates more than $Z$ dollars in a single year, she will receive a tax credit of $C\% $ on the amount over $Z$ dollars. The tax credit is immediately deposited into her bank account upon making the donation. Currently, it is the start of year $1$.

Money in Nicole’s bank account grows at an interest rate of $R\% $ compounded annually. That is, if the money in her account is $m$ dollars at the start of a year (after she possibly donates and receives tax credits), the money at the end of the year (and the start of the next year) will be $m \cdot (1+R/100)$ dollars.

Help Nicole find the maximum amount of money she could have at the end of year $N$ while donating to her favorite charity in the manner described.


The input consists of $6$ integers $N, X, Y, Z, C, R$ as described above. ($1\leq N\leq 300$, $Y\cdot N\leq X\leq 10^9$, $1\leq Y\leq 10^9$, $0\leq Z\leq 10^9$, $0 \leq C \leq 100$, $0 \leq R \leq 100$)


Output a single number with the answer. The answer is guaranteed to be a non-negative number not exceeding $10^{18}$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

Sample Input 1 Sample Output 1
2 100 10 5 10 1
Sample Input 2 Sample Output 2
2 100 10 0 10 1
CPU Time limit 1 second
Memory limit 1024 MB
Wenli Looi
Source Calgary Collegiate Programming Contest 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in