Suppose that you are selling steel rods, and you know rods of different lengths can be sold for different price, as listed in the table below. To maximize profit, you to consider cutting a long rod Into multiple short pieces. (Cutting is free and all lengths are integral numbers.) For example, for a rod that is 6-feet long, you would want to cut it into two 3-feet long pieces, resulting in a total price of 14 dollars. (If you do not cut, the price is $13; cutting it into 4 times 1-fooc long pieces, the total price would be $6; 3 x 2 foot would give you $12:1 times 2-foot and 1 times 4-feet would be $13, etc.) Design a dynamic programing algorithm to find an optimal cut for a rod of length n, and use your algorithm to find the optimal price for rods with lengths equal to 13, 14, and 15. For full credit, show the recurrence, pseudocode, the dynamic programming table, the optimal value and a cut that can result in the optimal value