1
class Solution:
2
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
3
        price = {
4
            (dimension_price[0], dimension_price[1]): dimension_price[2]
5
            for dimension_price in prices
6
        }
7
        DP = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
8

9
        def solve(h: int, v: int) -> int:
10
            if DP[h][v] != -1:
11
                return DP[i][j]
12

13
            ans = price.get((h, v), 0)
14

15
            for i in range(1, 1 + h // 2):
16
                ans = max(
17
                    ans,
18
                    (DP[i][v] if DP[i][v] != -1 else solve(i, v))
19
                    + (DP[h - i][v] if DP[h - i][v] != -1 else solve(h - i, v)),
20
                )
21

22
            for j in range(1, 1 + v // 2):
23
                ans = max(
24
                    ans,
25
                    (DP[h][j] if DP[h][j] != -1 else solve(h, j))
26
                    + (DP[h][v - j] if DP[h][v - j] != -1 else solve(h, v - j)),
27
                )
28

29
            DP[h][v] = ans
30

31
            return ans
32

33
        return solve(m, n)