You start a new tech business and you reach the point where you have offices both in the east coast and in the west coast. There are different operating costs involved in running your business in each location, so you may need to move back and forth across the coasts in order to minimize the total costs. However, there are moving costs involved in traveling from one coast to the other which complicate your problem. More formally, for each month i = 1,...., n you have an operating cost e_i associated with running your business in the east coast during that month and an operating cost w_i for the west coast. You can begin working in either coast, but after any subsequent travel from one coast to another you suffer a fixed travel cost of c. Given input {e₁,...,e_n}, {w₁,....,w_n} and c, provide a O(n) time algorithm that outputs a plan defining which coast you will work from each month, and minimizes your total cost (operating costs plus travel costs).

For example, if the number of months was n = 5, a possible plan could be to work from the east coast during the rst two months, then spend the next two months working from the west coast, and return to the east coast for the fth and nal month. The total cost in this case would be , where the two costs of c are due to the change of coast. Provide detailed pseudocode for your proposed algorithm, as well as an explanation regarding why it works and why its running time is indeed O(n).