Maximize Revenue from Rectangular Wood Cuts

### Problem A board has height `m` and width `n`. Each entry in `prices` gives an exact height, width and sale value. You may repeatedly cut a current rectangle all the way across its height or width, splitting it into two rectangles. Sell any resulting pieces with listed dimensions; repeated pieces of a listed shape may each be sold. You may leave other pieces unsold. A piece cannot be rotated to exchange its height and width. Return the greatest total revenue. ```cpp class Solution { public: long long sellingWood(int m, int n, vector<vector<int>>& prices); }; ``` ### Examples **Example 1:** ```text Input: m = 2, n = 2, prices = [[1,1,3],[2,2,10]] Output: 12 Explanation: Four 1-by-1 pieces sell for 12, exceeding the direct 2-by-2 price of 10. ``` **Example 2:** ```text Input: m = 2, n = 3, prices = [[1,2,4]] Output: 8 Explanation: Cut two horizontal strips, then take a 1-by-2 piece from each. Rotation is not allowed, so no 2-by-1 sale is available. ``` ### Constraints - `1 <= m, n <= 200`. - `1 <= prices.length <= 20000`; entries have [height, width, price]. - `1 <= height <= m`, `1 <= width <= n`, `1 <= price <= 10^6`. - Listed (height, width) shapes are pairwise distinct. ### Clarifying Questions - Can the same listed shape be sold more than once? Yes; offers are not consumed. - Must every piece be sold? No; unsold pieces contribute zero. - Can height and width be exchanged? No, rotation is prohibited. - Must a cut cross the whole original board? It must cross the whole current rectangle being cut. ```hint Check the boundary Check whether a height-by-width offer also applies after the dimensions are exchanged. ```