Commuting to optimize profit Suppose you run a company with two offices, one in Washington and the other in San Francisco Each week, you must choose where to work, and your choice will ailect your pront: in week i, you will make DCi dollars if you work in Washington or SFi dollars if you work in San Francisco. While you clearly would like to work in the location with the higher profit, each flight from Washington to San Francisco (or vice versa) costs S1000. Given lists (DC1,... , DCn) and (SF1,... , SFn), your goal is to find a schedule that maximizes your total profit, taking transportation costs into account. Since you live in Washington, your schedule must start and end there (a) An obvious greedy strategy is to always work in the office with the higher profit. Give a (minimal) example showing that this strategy is not always optimal (b) Design a polynomial-time algorithm that finds the maximum total profit. Justify your algorithm's correctness and establish its running time. To get full credit for your solution, you should make your running time as small as possible