4. In class, we have considered 1-dimensional rod cutting problem. For this question we consider a (wo dimensional version of this protilemi. Assume, you are giveri a rexilarggular piexe of sheen sheel with dimenzion X x Y, where X and I are poeitive integers; you are also given a lizt of products that can be made using steel sheets. For each product i [1, n], you know the dimension a, x b; of steel sheet, and the value of the product, v. Note that, a, and b; are positive integers. You have a machine that can cut a stcel shoet cither vertically or horizontally (all the way to the other prcd) so that, alleer the cul bolh the pieces are of reclangular shape. Cosil of an cul is o (amolher positive integeri for each unit length. For example, for a sheet of size X X Y if you cut parallel to the side with length X, the cutting cost is c.X. Now, design an algorithm that determines the best return on the X x Y piece of steel sheet. Note that, you are free to make as many copies of a given product, or none. (15)