You are given two integers m and n representing the dimensions of a rectangular piece of wood of height m and width n. You are also given a $2$D integer array prices, where prices[i] = $[h_i, w_i, price_i]$ indicates that a rectangular piece of wood of height h_i and width w_i can be sold for price_i money.

You can perform any number of horizontal or vertical cuts on a piece of wood to divide it into two smaller rectangular pieces. Each resulting piece can subsequently be cut further in the same manner. Any piece of wood with dimensions matching an entry in prices can be sold. A piece can also be left uncut or unsold.

Return the maximum amount of money that can be earned after cutting and selling the pieces.

Note: Pieces of wood cannot be rotated. A piece of wood of height h and width w is not equivalent to a piece of wood of height w and width h unless h equals w.

Constraints:

• $1 \leq$ m, n $\leq 200$

• $1 \leq$ prices.length $\leq 2 imes 10^4$

• prices[i].length $= 3$

• $1 \leq$ h_i $\leq$ m

• $1 \leq$ w_i $\leq$ n

• $1 \leq$ price_i $\leq 10^6$

• All the shapes of wood (h_i, w_i) are pairwise distinct.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.