Lady Gaga has come to you for advice. She has balances at three department stores as shown in the table below. The monthly interest rates vary between stores as shown. She wishes to pay off all three accounts by the end of three months. She will allot up to $40000 dollars for each month’s total payments. Your job is to determine how much she pays on each account in each month so that all the balances are zero at the end of three months and the total amount paid is minimized.

Store Balance ($) Monthly Interest Rate (%)

Table

Saks Fifth Avenue 20000 0.5

Bloomingdale’s 50000 1

Macy’s 40000 1.5

The payments and new balances are related to the interest rates. If, for example, Lady Gaga paid $5000 on her Sak’s bill during month 1 her balance at the beginning of month 2 would be:

$20000-$5000+0.005($20000)

A similar recursion is applicable for each store and each month:

New Balance= Previous balance –– Payment + interest rate*previous balance