1
class Solution {
2
  public long sellingWood(int m, int n, int[][] prices) {
3
    long[][] dp = new long[m + 1][n + 1];
4
    for (int[] price : prices) {
5
      dp[price[0]][price[1]] = price[2];
6
    }
7
    for (int i = 1; i < m + 1; i++) {
8
      for (int j = 1; j < n + 1; j++) {
9
        // all horizontal
10
        for (int k = 1; k <= i / 2; k++) {
11
          dp[i][j] = Math.max(dp[i][j], dp[i - k][j] + dp[k][j]);
12
        }
13
        // all vertical
14
        for (int k = 1; k <= j / 2; k++) {
15
          dp[i][j] = Math.max(dp[i][j], dp[i][j - k] + dp[i][k]);
16
        }
17
      }
18
    }
19

20
    return dp[m][n];
21
  }
22
}