You are given two integers m and n that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array prices , where prices[i] = [h _i , w _i , price _i ] indicates you can sell a rectangular piece of wood of height h _i and width w _i for price _i dollars.
To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to prices . You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width.
Return the maximum money you can earn after cutting an m x n piece of wood .
Note that you can cut the piece of wood as many times as you want.
1 <= m, n <= 2001 <= prices.length <= 2 * 10 ^4prices[i].length == 31 <= h _i <= m1 <= w _i <= n1 <= price _i <= 10 ^6All the shapes of wood (h _i , w _i ) are pairwise distinct .