bowang0911/leetcode huggingface dataset:
Replace Elements in an Array

You are given a **0-indexed** array `nums` that consists of `n` **distinct** positive integers. Apply `m` operations to this array, where in the `ith` operation you replace the number `operations[i][0]` with `operations[i][1]`.

It is guaranteed that in the `ith` operation:

*   `operations[i][0]` **exists** in `nums`.
*   `operations[i][1]` does **not** exist in `nums`.

Return _the array obtained after applying all the operations_.

**Example 1:**

**Input:** nums = \[1,2,4,6\], operations = \[\[1,3\],\[4,7\],\[6,1\]\]
**Output:** \[3,2,7,1\]
**Explanation:** We perform the following operations on nums:
- Replace the number 1 with 3. nums becomes \[**3**,2,4,6\].
- Replace the number 4 with 7. nums becomes \[3,2,**7**,6\].
- Replace the number 6 with 1. nums becomes \[3,2,7,**1**\].
We return the final array \[3,2,7,1\].

**Example 2:**

**Input:** nums = \[1,2\], operations = \[\[1,3\],\[2,1\],\[3,2\]\]
**Output:** \[2,1\]
**Explanation:** We perform the following operations to nums:
- Replace the number 1 with 3. nums becomes \[**3**,2\].
- Replace the number 2 with 1. nums becomes \[3,**1**\].
- Replace the number 3 with 2. nums becomes \[**2**,1\].
We return the array \[2,1\].

**Constraints:**

*   `n == nums.length`
*   `m == operations.length`
*   `1 <= n, m <= 105`
*   All the values of `nums` are **distinct**.
*   `operations[i].length == 2`
*   `1 <= nums[i], operations[i][0], operations[i][1] <= 106`
*   `operations[i][0]` will exist in `nums` when applying the `ith` operation.
*   `operations[i][1]` will not exist in `nums` when applying the `ith` operation.
Jump Game VIII

You are given a **0-indexed** integer array `nums` of length `n`. You are initially standing at index `0`. You can jump from index `i` to index `j` where `i < j` if:

*   `nums[i] <= nums[j]` and `nums[k] < nums[i]` for all indexes `k` in the range `i < k < j`, or
*   `nums[i] > nums[j]` and `nums[k] >= nums[i]` for all indexes `k` in the range `i < k < j`.

You are also given an integer array `costs` of length `n` where `costs[i]` denotes the cost of jumping **to** index `i`.

Return _the **minimum** cost to jump to the index_ `n - 1`.

**Example 1:**

**Input:** nums = \[3,2,4,4,1\], costs = \[3,7,6,4,2\]
**Output:** 8
**Explanation:** You start at index 0.
- Jump to index 2 with a cost of costs\[2\] = 6.
- Jump to index 4 with a cost of costs\[4\] = 2.
The total cost is 8. It can be proven that 8 is the minimum cost needed.
Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4.
These have a total cost of 9 and 12, respectively.

**Example 2:**

**Input:** nums = \[0,1,2\], costs = \[1,1,1\]
**Output:** 2
**Explanation:** Start at index 0.
- Jump to index 1 with a cost of costs\[1\] = 1.
- Jump to index 2 with a cost of costs\[2\] = 1.
The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums\[0\] <= nums\[1\].

**Constraints:**

*   `n == nums.length == costs.length`
*   `1 <= n <= 105`
*   `0 <= nums[i], costs[i] <= 105`
Strong Password Checker II

A password is said to be **strong** if it satisfies all the following criteria:

*   It has at least `8` characters.
*   It contains at least **one lowercase** letter.
*   It contains at least **one uppercase** letter.
*   It contains at least **one digit**.
*   It contains at least **one special character**. The special characters are the characters in the following string: `"!@#$%^&*()-+ "`.
*   It does **not** contain `2` of the same character in adjacent positions (i.e., `"aab "` violates this condition, but `"aba "` does not).

Given a string `password`, return `true` _if it is a **strong** password_. Otherwise, return `false`.

**Example 1:**

**Input:** password =  "IloveLe3tcode! "
**Output:** true
**Explanation:** The password meets all the requirements. Therefore, we return true.

**Example 2:**

**Input:** password =  "Me+You--IsMyDream "
**Output:** false
**Explanation:** The password does not contain a digit and also contains 2 of the same character in adjacent positions. Therefore, we return false.

**Example 3:**

**Input:** password =  "1aB! "
**Output:** false
**Explanation:** The password does not meet the length requirement. Therefore, we return false.

**Constraints:**

*   `1 <= password.length <= 100`
*   `password` consists of letters, digits, and special characters: `"!@#$%^&*()-+ "`.
Successful Pairs of Spells and Potions

You are given two positive integer arrays `spells` and `potions`, of length `n` and `m` respectively, where `spells[i]` represents the strength of the `ith` spell and `potions[j]` represents the strength of the `jth` potion.

You are also given an integer `success`. A spell and potion pair is considered **successful** if the **product** of their strengths is **at least** `success`.

Return _an integer array_ `pairs` _of length_ `n` _where_ `pairs[i]` _is the number of **potions** that will form a successful pair with the_ `ith` _spell._

**Example 1:**

**Input:** spells = \[5,1,3\], potions = \[1,2,3,4,5\], success = 7
**Output:** \[4,0,3\]
**Explanation:**
- 0th spell: 5 \* \[1,2,3,4,5\] = \[5,**10**,**15**,**20**,**25**\]. 4 pairs are successful.
- 1st spell: 1 \* \[1,2,3,4,5\] = \[1,2,3,4,5\]. 0 pairs are successful.
- 2nd spell: 3 \* \[1,2,3,4,5\] = \[3,6,**9**,**12**,**15**\]. 3 pairs are successful.
Thus, \[4,0,3\] is returned.

**Example 2:**

**Input:** spells = \[3,1,2\], potions = \[8,5,8\], success = 16
**Output:** \[2,0,2\]
**Explanation:**
- 0th spell: 3 \* \[8,5,8\] = \[**24**,15,**24**\]. 2 pairs are successful.
- 1st spell: 1 \* \[8,5,8\] = \[8,5,8\]. 0 pairs are successful. 
- 2nd spell: 2 \* \[8,5,8\] = \[**16**,10,**16**\]. 2 pairs are successful. 
Thus, \[2,0,2\] is returned.

**Constraints:**

*   `n == spells.length`
*   `m == potions.length`
*   `1 <= n, m <= 105`
*   `1 <= spells[i], potions[i] <= 105`
*   `1 <= success <= 1010`
Match Substring After Replacement

You are given two strings `s` and `sub`. You are also given a 2D character array `mappings` where `mappings[i] = [oldi, newi]` indicates that you may perform the following operation **any** number of times:

*   **Replace** a character `oldi` of `sub` with `newi`.

Each character in `sub` **cannot** be replaced more than once.

Return `true` _if it is possible to make_ `sub` _a substring of_ `s` _by replacing zero or more characters according to_ `mappings`. Otherwise, return `false`.

A **substring** is a contiguous non-empty sequence of characters within a string.

**Example 1:**

**Input:** s =  "fool3e7bar ", sub =  "leet ", mappings = \[\[ "e ", "3 "\],\[ "t ", "7 "\],\[ "t ", "8 "\]\]
**Output:** true
**Explanation:** Replace the first 'e' in sub with '3' and 't' in sub with '7'.
Now sub =  "l3e7 " is a substring of s, so we return true.

**Example 2:**

**Input:** s =  "fooleetbar ", sub =  "f00l ", mappings = \[\[ "o ", "0 "\]\]
**Output:** false
**Explanation:** The string  "f00l " is not a substring of s and no replacements can be made.
Note that we cannot replace '0' with 'o'.

**Example 3:**

**Input:** s =  "Fool33tbaR ", sub =  "leetd ", mappings = \[\[ "e ", "3 "\],\[ "t ", "7 "\],\[ "t ", "8 "\],\[ "d ", "b "\],\[ "p ", "b "\]\]
**Output:** true
**Explanation:** Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
Now sub =  "l33tb " is a substring of s, so we return true.

**Constraints:**

*   `1 <= sub.length <= s.length <= 5000`
*   `0 <= mappings.length <= 1000`
*   `mappings[i].length == 2`
*   `oldi != newi`
*   `s` and `sub` consist of uppercase and lowercase English letters and digits.
*   `oldi` and `newi` are either uppercase or lowercase English letters or digits.

0 <= i < j < n and nums\[i\] % k + nums\[j\] % k == k.
Count Subarrays With Score Less Than K

The **score** of an array is defined as the **product** of its sum and its length.

*   For example, the score of `[1, 2, 3, 4, 5]` is `(1 + 2 + 3 + 4 + 5) * 5 = 75`.

Given a positive integer array `nums` and an integer `k`, return _the **number of non-empty subarrays** of_ `nums` _whose score is **strictly less** than_ `k`.

A **subarray** is a contiguous sequence of elements within an array.

**Example 1:**

**Input:** nums = \[2,1,4,3,5\], k = 10
**Output:** 6
**Explanation:**
The 6 subarrays having scores less than 10 are:
- \[2\] with score 2 \* 1 = 2.
- \[1\] with score 1 \* 1 = 1.
- \[4\] with score 4 \* 1 = 4.
- \[3\] with score 3 \* 1 = 3. 
- \[5\] with score 5 \* 1 = 5.
- \[2,1\] with score (2 + 1) \* 2 = 6.
Note that subarrays such as \[1,4\] and \[4,3,5\] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.

**Example 2:**

**Input:** nums = \[1,1,1\], k = 5
**Output:** 5
**Explanation:**
Every subarray except \[1,1,1\] has a score less than 5.
\[1,1,1\] has a score (1 + 1 + 1) \* 3 = 9, which is greater than 5.
Thus, there are 5 subarrays having scores less than 5.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
*   `1 <= k <= 1015`
Calculate Amount Paid in Taxes

You are given a **0-indexed** 2D integer array `brackets` where `brackets[i] = [upperi, percenti]` means that the `ith` tax bracket has an upper bound of `upperi` and is taxed at a rate of `percenti`. The brackets are **sorted** by upper bound (i.e. `upperi-1 < upperi` for `0 < i < brackets.length`).

Tax is calculated as follows:

*   The first `upper0` dollars earned are taxed at a rate of `percent0`.
*   The next `upper1 - upper0` dollars earned are taxed at a rate of `percent1`.
*   The next `upper2 - upper1` dollars earned are taxed at a rate of `percent2`.
*   And so on.

You are given an integer `income` representing the amount of money you earned. Return _the amount of money that you have to pay in taxes._ Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** brackets = \[\[3,50\],\[7,10\],\[12,25\]\], income = 10
**Output:** 2.65000
**Explanation:**
Based on your income, you have 3 dollars in the 1st tax bracket, 4 dollars in the 2nd tax bracket, and 3 dollars in the 3rd tax bracket.
The tax rate for the three tax brackets is 50%, 10%, and 25%, respectively.
In total, you pay $3 \* 50% + $4 \* 10% + $3 \* 25% = $2.65 in taxes.

**Example 2:**

**Input:** brackets = \[\[1,0\],\[4,25\],\[5,50\]\], income = 2
**Output:** 0.25000
**Explanation:**
Based on your income, you have 1 dollar in the 1st tax bracket and 1 dollar in the 2nd tax bracket.
The tax rate for the two tax brackets is 0% and 25%, respectively.
In total, you pay $1 \* 0% + $1 \* 25% = $0.25 in taxes.

**Example 3:**

**Input:** brackets = \[\[2,50\]\], income = 0
**Output:** 0.00000
**Explanation:**
You have no income to tax, so you have to pay a total of $0 in taxes.

**Constraints:**

*   `1 <= brackets.length <= 100`
*   `1 <= upperi <= 1000`
*   `0 <= percenti <= 100`
*   `0 <= income <= 1000`
*   `upperi` is sorted in ascending order.
*   All the values of `upperi` are **unique**.
*   The upper bound of the last tax bracket is greater than or equal to `income`.
Minimum Path Cost in a Grid

You are given a **0-indexed** `m x n` integer matrix `grid` consisting of **distinct** integers from `0` to `m * n - 1`. You can move in this matrix from a cell to any other cell in the **next** row. That is, if you are in cell `(x, y)` such that `x < m - 1`, you can move to any of the cells `(x + 1, 0)`, `(x + 1, 1)`, ..., `(x + 1, n - 1)`. **Note** that it is not possible to move from cells in the last row.

Each possible move has a cost given by a **0-indexed** 2D array `moveCost` of size `(m * n) x n`, where `moveCost[i][j]` is the cost of moving from a cell with value `i` to a cell in column `j` of the next row. The cost of moving from cells in the last row of `grid` can be ignored.

The cost of a path in `grid` is the **sum** of all values of cells visited plus the **sum** of costs of all the moves made. Return _the **minimum** cost of a path that starts from any cell in the **first** row and ends at any cell in the **last** row._

**Example 1:**

**Input:** grid = \[\[5,3\],\[4,0\],\[2,1\]\], moveCost = \[\[9,8\],\[1,5\],\[10,12\],\[18,6\],\[2,4\],\[14,3\]\]
**Output:** 17
**Explanation:** The path with the minimum possible cost is the path 5 -> 0 -> 1.
- The sum of the values of cells visited is 5 + 0 + 1 = 6.
- The cost of moving from 5 to 0 is 3.
- The cost of moving from 0 to 1 is 8.
So the total cost of the path is 6 + 3 + 8 = 17.

**Example 2:**

**Input:** grid = \[\[5,1,2\],\[4,0,3\]\], moveCost = \[\[12,10,15\],\[20,23,8\],\[21,7,1\],\[8,1,13\],\[9,10,25\],\[5,3,2\]\]
**Output:** 6
**Explanation:** The path with the minimum possible cost is the path 2 -> 3.
- The sum of the values of cells visited is 2 + 3 = 5.
- The cost of moving from 2 to 3 is 1.
So the total cost of this path is 5 + 1 = 6.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `2 <= m, n <= 50`
*   `grid` consists of distinct integers from `0` to `m * n - 1`.
*   `moveCost.length == m * n`
*   `moveCost[i].length == n`
*   `1 <= moveCost[i][j] <= 100`
Fair Distribution of Cookies

You are given an integer array `cookies`, where `cookies[i]` denotes the number of cookies in the `ith` bag. You are also given an integer `k` that denotes the number of children to distribute **all** the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.

The **unfairness** of a distribution is defined as the **maximum** **total** cookies obtained by a single child in the distribution.

Return _the **minimum** unfairness of all distributions_.

**Example 1:**

**Input:** cookies = \[8,15,10,20,8\], k = 2
**Output:** 31
**Explanation:** One optimal distribution is \[8,15,8\] and \[10,20\]
- The 1st child receives \[8,15,8\] which has a total of 8 + 15 + 8 = 31 cookies.
- The 2nd child receives \[10,20\] which has a total of 10 + 20 = 30 cookies.
The unfairness of the distribution is max(31,30) = 31.
It can be shown that there is no distribution with an unfairness less than 31.

**Example 2:**

**Input:** cookies = \[6,1,3,2,2,4,1,2\], k = 3
**Output:** 7
**Explanation:** One optimal distribution is \[6,1\], \[3,2,2\], and \[4,1,2\]
- The 1st child receives \[6,1\] which has a total of 6 + 1 = 7 cookies.
- The 2nd child receives \[3,2,2\] which has a total of 3 + 2 + 2 = 7 cookies.
- The 3rd child receives \[4,1,2\] which has a total of 4 + 1 + 2 = 7 cookies.
The unfairness of the distribution is max(7,7,7) = 7.
It can be shown that there is no distribution with an unfairness less than 7.

**Constraints:**

*   `2 <= cookies.length <= 8`
*   `1 <= cookies[i] <= 105`
*   `2 <= k <= cookies.length`
Naming a Company

You are given an array of strings `ideas` that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:

1.  Choose 2 **distinct** names from `ideas`, call them `ideaA` and `ideaB`.
2.  Swap the first letters of `ideaA` and `ideaB` with each other.
3.  If **both** of the new names are not found in the original `ideas`, then the name `ideaA ideaB` (the **concatenation** of `ideaA` and `ideaB`, separated by a space) is a valid company name.
4.  Otherwise, it is not a valid name.

Return _the number of **distinct** valid names for the company_.

**Example 1:**

**Input:** ideas = \[ "coffee ", "donuts ", "time ", "toffee "\]
**Output:** 6
**Explanation:** The following selections are valid:
- ( "coffee ",  "donuts "): The company name created is  "doffee conuts ".
- ( "donuts ",  "coffee "): The company name created is  "conuts doffee ".
- ( "donuts ",  "time "): The company name created is  "tonuts dime ".
- ( "donuts ",  "toffee "): The company name created is  "tonuts doffee ".
- ( "time ",  "donuts "): The company name created is  "dime tonuts ".
- ( "toffee ",  "donuts "): The company name created is  "doffee tonuts ".
Therefore, there are a total of 6 distinct company names.

The following are some examples of invalid selections:
- ( "coffee ",  "time "): The name  "toffee " formed after swapping already exists in the original array.
- ( "time ",  "toffee "): Both names are still the same after swapping and exist in the original array.
- ( "coffee ",  "toffee "): Both names formed after swapping already exist in the original array.

**Example 2:**

**Input:** ideas = \[ "lack ", "back "\]
**Output:** 0
**Explanation:** There are no valid selections. Therefore, 0 is returned.

**Constraints:**

*   `2 <= ideas.length <= 5 * 104`
*   `1 <= ideas[i].length <= 10`
*   `ideas[i]` consists of lowercase English letters.
*   All the strings in `ideas` are **unique**.
Check for Contradictions in Equations

You are given a 2D array of strings `equations` and an array of real numbers `values`, where `equations[i] = [Ai, Bi]` and `values[i]` means that `Ai / Bi = values[i]`.

Determine if there exists a contradiction in the equations. Return `true` _if there is a contradiction, or_ `false` _otherwise_.

**Note**:

*   When checking if two numbers are equal, check that their **absolute difference** is less than `10-5`.
*   The testcases are generated such that there are no cases targeting precision, i.e. using `double` is enough to solve the problem.

**Example 1:**

**Input:** equations = \[\[ "a ", "b "\],\[ "b ", "c "\],\[ "a ", "c "\]\], values = \[3,0.5,1.5\]
**Output:** false
**Explanation:**
The given equations are: a / b = 3, b / c = 0.5, a / c = 1.5
There are no contradictions in the equations. One possible assignment to satisfy all equations is:
a = 3, b = 1 and c = 2.

**Example 2:**

**Input:** equations = \[\[ "le ", "et "\],\[ "le ", "code "\],\[ "code ", "et "\]\], values = \[2,5,0.5\]
**Output:** true
**Explanation:**
The given equations are: le / et = 2, le / code = 5, code / et = 0.5
Based on the first two equations, we get code / et = 0.4.
Since the third equation is code / et = 0.5, we get a contradiction.

**Constraints:**

*   `1 <= equations.length <= 100`
*   `equations[i].length == 2`
*   `1 <= Ai.length, Bi.length <= 5`
*   `Ai`, `Bi` consist of lowercase English letters.
*   `equations.length == values.length`
*   `0.0 < values[i] <= 10.0`
*   `values[i]` has a maximum of 2 decimal places.
Greatest English Letter in Upper and Lower Case

Given a string of English letters `s`, return _the **greatest** English letter which occurs as **both** a lowercase and uppercase letter in_ `s`. The returned letter should be in **uppercase**. If no such letter exists, return _an empty string_.

An English letter `b` is **greater** than another letter `a` if `b` appears **after** `a` in the English alphabet.

**Example 1:**

**Input:** s =  "l**Ee**TcOd**E** "
**Output:**  "E "
**Explanation:**
The letter 'E' is the only letter to appear in both lower and upper case.

**Example 2:**

**Input:** s =  "a**rR**AzFif "
**Output:**  "R "
**Explanation:**
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.

**Example 3:**

**Input:** s =  "AbCdEfGhIjK "
**Output:**  " "
**Explanation:**
There is no letter that appears in both lower and upper case.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of lowercase and uppercase English letters.
Sum of Numbers With Units Digit K

Given two integers `num` and `k`, consider a set of positive integers with the following properties:

*   The units digit of each integer is `k`.
*   The sum of the integers is `num`.

Return _the **minimum** possible size of such a set, or_ `-1` _if no such set exists._

Note:

*   The set can contain multiple instances of the same integer, and the sum of an empty set is considered `0`.
*   The **units digit** of a number is the rightmost digit of the number.

**Example 1:**

**Input:** num = 58, k = 9
**Output:** 2
**Explanation:**
One valid set is \[9,49\], as the sum is 58 and each integer has a units digit of 9.
Another valid set is \[19,39\].
It can be shown that 2 is the minimum possible size of a valid set.

**Example 2:**

**Input:** num = 37, k = 2
**Output:** -1
**Explanation:** It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.

**Example 3:**

**Input:** num = 0, k = 7
**Output:** 0
**Explanation:** The sum of an empty set is considered 0.

**Constraints:**

*   `0 <= num <= 3000`
*   `0 <= k <= 9`
Longest Binary Subsequence Less Than or Equal to K

You are given a binary string `s` and a positive integer `k`.

Return _the length of the **longest** subsequence of_ `s` _that makes up a **binary** number less than or equal to_ `k`.

Note:

*   The subsequence can contain **leading zeroes**.
*   The empty string is considered to be equal to `0`.
*   A **subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

**Example 1:**

**Input:** s =  "1001010 ", k = 5
**Output:** 5
**Explanation:** The longest subsequence of s that makes up a binary number less than or equal to 5 is  "00010 ", as this number is equal to 2 in decimal.
Note that  "00100 " and  "00101 " are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.

**Example 2:**

**Input:** s =  "00101001 ", k = 1
**Output:** 6
**Explanation:**  "000001 " is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s[i]` is either `'0'` or `'1'`.
*   `1 <= k <= 109`
Selling Pieces of Wood

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] = [hi, wi, pricei]` indicates you can sell a rectangular piece of wood of height `hi` and width `wi` for `pricei` 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.

**Example 1:**

**Input:** m = 3, n = 5, prices = \[\[1,4,2\],\[2,2,7\],\[2,1,3\]\]
**Output:** 19
**Explanation:** The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 \* 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 \* 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 \* 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.

**Example 2:**

**Input:** m = 4, n = 6, prices = \[\[3,2,10\],\[1,4,2\],\[4,1,3\]\]
**Output:** 32
**Explanation:** The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 \* 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 \* 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.

**Constraints:**

*   `1 <= m, n <= 200`
*   `1 <= prices.length <= 2 * 104`
*   `prices[i].length == 3`
*   `1 <= hi <= m`
*   `1 <= wi <= n`
*   `1 <= pricei <= 106`
*   All the shapes of wood `(hi, wi)` are pairwise **distinct**.