Suppose you have a business which caters to Chicago and St. Louis. Each month, you can choose to either run your business from an office in Chicago, or from an office in St. Louis. In month i, you incur an operating cost of Ci if you run the business out of Chicago, and a cost of Si if you instead run the business out of St. Louis. Each time you decide to switch between cities between two consecutive months, you incur a moving cost of M. Given a sequence of n months, a plan is a sequence of n locations (each one equal to either Chicago or St. Louis) such that the ith location indicates the city in which you will be based in the ith month. The cost of a plan is the sum of the operating costs for each of the n months, plus a moving cost M for each time you switch cities. The plan can begin in either city. ?

Your task is as follows: Given a value for M and sequences (C1; C2; ; ; ; Cn) and (S1; S2; ; ; ; Sn), give an efficient dynamic programming algorithm which returns the cost of an optimal plan for the n months in question.