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 XY, where X and Y are poeitive integers; you are also given a lizt of n products that can be made using steel sheets. For each product i[1,n], you know the dimension aibi of steel sheet, and the value of the product, vi. Note that, ai, and bi 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 XY if you cut parallel to the side with length X, the cutting cost is cX. Now, design an algorithm that determines the best return on the XY piece of steel sheet. Note that, you are free to make as many copies of a given product, or none. (15)