We are given n currencies and an exchange rate rij for any pair of currencies i an j. Namely, if we exchange 1 unit of currency i with currency j, we receive rij units of currency j. If we are given a source currency s and a target currency t, then we can go through a path of different currencies to reach t from s so as to maximize our profit. The markets can also charge an exchange fee depending on the number of exchanges we make. For example if the exchange fee is f(k) for making k exchanges and we start with 1 unit of currency s, then the path of exchanges s +t will yield rst f(1) units of currency t, whereas the path of exchanges s + i + j +t will yield r si x rij X rjt f(3) units of currency t. The problem is to find the sequence of exchanges that will maximize the amount of target currency t we can obtain for a given source currency s. (a) Define and prove the optimal substructure for this problem when there is no exchange fee (f(k) = 0 for all k). (b) Prove that it is possible to find an exchange fee schedule f(k) so that the optimal substructure you defined above will not hold anymore