Suppose you are consulting for a company that manufactures PC equipment and ships it to distributors all over the country. For each of the n next weeks, they have a projected supply si of equipment (measured in pounds), which has to be shipped by an air freight carrier. Each week’s supply can be carried by one of two air freight companies, A or B. − Company A charges a fixed rate r per pound, so it costs r ∗ si to ship a week’s supply (si) − Company B makes contracts for a fixed amount c per week, independent of the weight. However, contracts with company B must be made in blocks of four consecutive weeks at a time. A schedule, for the PC company, is a choice of air freight company (A or B) for each of the n weeks with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks at a time. The cost of the schedule is the total amount paid to companies A and B, according to the description above. You are asked to give a polynomial time algorithm that takes a sequence of supply values s1, s2,…, sn and returns a schedule of minimum cost. In order to achieve this, you need to answer the following questions:Determine and prove the optimal substructure of the problem and write a recursive formula of an optimal solution (i. e., define the variable that you wish to optimize and explain how a solution to computing it can be obtained from solutions to subproblems). Submit: the recursive formula, along with definitions and explanations on what is computed. Write an algorithm that computes an optimal solution to this problem, based on the recurrence above. Implement your algorithm in C/C++ and run it on the following values: - r = 1, c = 10, the sequence of si values: 11, 9, 9, 12, 12, 12, 12, 9, 9, 11.