1
class Solution {
2
 private:
3
  long long f(int row, int col, map<pair<int, int>, long long> &mp) {
4
    // Base case is tackled in this line
5
    long long ans = mp[{row, col}];
6

7
    for (int i = 1; i < row; i++) // Partitions Row-wise
8
      ans = max(ans, f(i, col, mp) + f(row - i, col, mp));
9

10
    for (int j = 1; j < col; j++) // Partitions Column-wise
11
      ans = max(ans, f(row, j, mp) + f(row, col - j, mp));
12

13
    return ans;
14
  }
15

16
 public:
17
  long long sellingWood(int m, int n, vector<vector<int>> &prices) {
18
    // Declaring the HashMap
19
    map<pair<int, int>, long long> mp;
20

21
    // Storing Prices in HashMap where {height,width} of wood is key and {Price}
22
    // is value
23
    for (int i = 0; i < prices.size(); i++) mp[{prices[i][0], prices[i][1]}] = prices[i][2];
24

25
    return f(m, n, mp);
26
  }
27
};