You are given a rectangular piece of cloth with dimensions $xY,$ where $x$ and $Y$ are positive

integers, and a list of $n$ products that can be made using the cloth. For each product iin$[1,$dots,$n]$ you know that a rectangle of cloth of dimensions $a_i{b}_i$ is needed and that the final selling price of the product is $c_i.$ Assume the $a_i,b_i,$ and $c_i$ are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design a dynamic programming algorithm that determines the best return on the $xY$ piece of cloth, that is$,$ a strategy for cutting the cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired. Write the definition, base case, solution and formula.