Problem 2: Feeding the Prisoners [20 points] Fruitcake Frank's first in-prison job assignment is to manage the contracts for the prison's food suppliers. The prison contracts alternately with two different suppliers, Jailhouse Grub and Lockup Eats. For each of n weeks, the prison needs to purchase some number of meals, though the number may vary across weeks. That is, in week i, the prison needs to purchase m, meals. Both suppliers have the same per-meal cost (c), but they each have a different way of doing a contract, which results in different fee schedules. Jailhouse Grub offers contracts for exactly four week blocks and charges a fixed fee per week of the contract, regardless of the number of meals they have to supply (we'll call Jailhouse Grub's fee fA). Lockup Eats charges a fixed fee per meal supplied but will contract one week at a time (we'll call Lockup Eats's fee fB). That is, every contract with Jailhouse Grub must be done for four consecutive weeks, but Lockup Eats can be contracted for individual weeks. Fruitcake's job is, given the number of meals needed for some n weeks, to figure out a schedule of contracts with Jailhouse Grub and Lockup Eats that is most cost efficient for the prison. For example, assume that the costs of each meal is c = $10, and the fees are: fA= $2000/week and fB = $2/meal. Given the following number of meals needed for the next n = 6 weeks: [800, 1000, 1500, 1200, 900, 700], the optimal schedule of contracts with Jailhouse Grub and Lockup Eats is [LE, JG, JG, JG, JG, LE], which results in the following costs: Week(s) 1 2-5 6 # Meals 800 4600 700 Supplier Lockup Eats Jailhouse Grub Lockup Eats Cost of Meals $8000 (800 x c) $46000 (4600 x c) $7000 (700 x c) Fee $1600 (800 fB) $8000 = (4 fA) $1400 (700x fB) You should give a polynomial time algorithm to create the schedule of contracts for n weeks, given c, fa, fB and the array m[1..n]. Your algorithm should return the schedule (i.e., which supplier to contract with on each week) as well as the total cost for all n weeks. State and briefly justify the runtime of your algorithm.