You have mined a large slab of marble from a quarry. For simplicity, suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You want to cut the slab into smaller rectangles of various sizes - some for kitchen counter tops, some for large sculpture projects, others for memorial headstones. You have a marble saw that can make either horizontal or vertical cuts across any rectangular slab. At any time, you can query the spot price P[x, y] of an x-inch by y-inch marble rectangle, for any positive integers x and y. These prices depend on customer demand, and people who buy marble counter tops are weird, so don’t make any assumptions about them; in particular, larger rectangles may have significantly smaller spot prices. Given the array of spot prices and the integers m and n as input, design a dynamic programming algorithm to compute how to subdivide an n × m marble slab to maximize your profit. Your solution must output both the maximum profit as well as the sequence of cuts necessary to obtain that profit. A sequence of cuts can be described as a sequence of tuples (V, x, ymin, ymax) for vertical cuts, (H, y, xmin, xmax) of horizontal cuts. For example, the rectangle depicted below has been subdivided via the sequence of cuts [(V, 10, 0, 13),(H, 8, 0, 10),(V, 4, 0, 8)]