ExpertSimulation & Finance50 points

How much does a yearly prepayment save?

A homeowner in Manchester has a loan with a fixed monthly payment. Every year, on the anniversary of the loan, she plans to send a lump sum to the bank. Before agreeing, she wants to see how many months and how much interest she saves compared with paying only the normal instalment.

Simulate month by month with the decimal module, rounding every amount to cents with halves up. Monthly rate = annual / 1200. In each month: interest = balance times monthly rate (rounded), added to the balance; then the payment is made. The payment is the fixed instalment, but if balance plus interest is not more than the instalment, the loan is cleared with a smaller last payment and the simulation ends. After the payment of every 12th, 24th, 36th... month, if the loan is still open, the lump sum is also paid, but never more than the remaining balance (if it clears the loan, the simulation ends).

Task: read four lines: principal, annual rate in percent, monthly instalment, and yearly lump sum (may be 0). The instalment is always larger than the first month's interest. Print three lines: Months: N (months until the loan is cleared, with the lump sum), Interest paid: X and Interest saved: Y (interest of the same loan with no lump sum, minus interest with the lump sum). Amounts have 2 decimals.

Sample tests

Input

250000
7.5
3000
10000

Expected output

Months: 86
Interest paid: 75267.34
Interest saved: 28975.08

Input

40000
9
1000
0

Expected output

Months: 48
Interest paid: 7735.51
Interest saved: 0.00

Your answer is also checked against 4 hidden tests.