<p>There is an <code>m x n</code> cake that needs to be cut into <code>1 x 1</code> pieces.</p>

<p>You are given integers <code>m</code>, <code>n</code>, and two arrays:</p>

<ul>
	<li><code>horizontalCut</code> of size <code>m - 1</code>, where <code>horizontalCut[i]</code> represents the cost to cut along the horizontal line <code>i</code>.</li>
	<li><code>verticalCut</code> of size <code>n - 1</code>, where <code>verticalCut[j]</code> represents the cost to cut along the vertical line <code>j</code>.</li>
</ul>

<p>In one operation, you can choose any piece of cake that is not yet a <code>1 x 1</code> square and perform one of the following cuts:</p>

<ol>
	<li>Cut along a horizontal line <code>i</code> at a cost of <code>horizontalCut[i]</code>.</li>
	<li>Cut along a vertical line <code>j</code> at a cost of <code>verticalCut[j]</code>.</li>
</ol>

<p>After the cut, the piece of cake is divided into two distinct pieces.</p>

<p>The cost of a cut depends only on the initial cost of the line and does not change.</p>

<p>Return the <strong>minimum</strong> total cost to cut the entire cake into <code>1 x 1</code> pieces.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]</span></p>

<p><strong>Output:</strong> <span class="example-io">13</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/06/04/ezgifcom-animated-gif-maker-1.gif" style="width: 280px; height: 320px;" /></p>

<ul>
	<li>Perform a cut on the vertical line 0 with cost 5, current total cost is 5.</li>
	<li>Perform a cut on the horizontal line 0 on <code>3 x 1</code> subgrid with cost 1.</li>
	<li>Perform a cut on the horizontal line 0 on <code>3 x 1</code> subgrid with cost 1.</li>
	<li>Perform a cut on the horizontal line 1 on <code>2 x 1</code> subgrid with cost 3.</li>
	<li>Perform a cut on the horizontal line 1 on <code>2 x 1</code> subgrid with cost 3.</li>
</ul>

<p>The total cost is <code>5 + 1 + 1 + 3 + 3 = 13</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">m = 2, n = 2, horizontalCut = [7], verticalCut = [4]</span></p>

<p><strong>Output:</strong> <span class="example-io">15</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>Perform a cut on the horizontal line 0 with cost 7.</li>
	<li>Perform a cut on the vertical line 0 on <code>1 x 2</code> subgrid with cost 4.</li>
	<li>Perform a cut on the vertical line 0 on <code>1 x 2</code> subgrid with cost 4.</li>
</ul>

<p>The total cost is <code>7 + 4 + 4 = 15</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= m, n &lt;= 20</code></li>
	<li><code>horizontalCut.length == m - 1</code></li>
	<li><code>verticalCut.length == n - 1</code></li>
	<li><code>1 &lt;= horizontalCut[i], verticalCut[i] &lt;= 10<sup>3</sup></code></li>
</ul>

class Solution:
    def minimumCostRectOld(self, x1, y1, x2, y2):
        res = self.cache.get((x1, y1, x2, y2))
        if res is not None:
            return res
        
        values = []
        for x in range(x1 + 1, x2):
            val = self.minimumCostRect(x1, y1, x, y2)
            val += self.horizontalCut[x - 1]
            val += self.minimumCostRect(x, y1, x2, y2)
            values.append(val)

        for y in range(y1 + 1, y2):
            val = self.minimumCostRect(x1, y1, x2, y)
            val += self.verticalCut[y - 1]
            val += self.minimumCostRect(x1, y, x2, y2)
            values.append(val)
        
        if len(values) == 0:
            return 0

        val = min(values)
        self.cache[(x1, y1, x2, y2)] = val
        return val

    def minimumCostRectOld2(self, x1, y1, x2, y2):
        res = self.cache.get((x1, y1, x2, y2))
        if res is not None:
            return res
        
        h_pairs = [(self.horizontalCut[x - 1], x) for x in range(x1 + 1, x2)]
        h_val = None
        if len(h_pairs) > 0:
            h_pair = max(h_pairs)
            h_x = h_pair[1]
            h_val = self.minimumCostRect(x1, y1, h_x, y2) + h_pair[0] + self.minimumCostRect(h_x, y1, x2, y2)

        v_pairs = [(self.verticalCut[y - 1], y) for y in range(y1 + 1, y2)]
        v_val = None
        if len(v_pairs) > 0:
            v_pair = max(v_pairs)
            v_y = v_pair[1]
            v_val = self.minimumCostRect(x1, y1, x2, v_y) + v_pair[0] + self.minimumCostRect(x1, v_y, x2, y2)

        val = None
        if h_val is None and v_val is None:
            return 0
        elif h_val is None:
            val = v_val
        elif v_val is None:
            val = h_val
        else:
            val = min(h_val, v_val)

        self.cache[(x1, y1, x2, y2)] = val
        return val

    def minimumCostRect(self, x1, y1, x2, y2):
        res = self.cache.get((x1, y1, x2, y2))
        if res is not None:
            return res
        
        h_tuples = [(self.horizontalCut[x - 1], x, True) for x in range(x1 + 1, x2)]
        v_tuples = [(self.verticalCut[y - 1], y, False) for y in range(y1 + 1, y2)]
        all_tuples = h_tuples + v_tuples
        if len(all_tuples) == 0:
            return 0

        max_tuple = max(all_tuples)
        horizontal = max_tuple[2]
        val = max_tuple[0]
        if horizontal:
            h_x = max_tuple[1]
            val += self.minimumCostRect(x1, y1, h_x, y2) + self.minimumCostRect(h_x, y1, x2, y2)
        else:
            v_y = max_tuple[1]
            val += self.minimumCostRect(x1, y1, x2, v_y) + self.minimumCostRect(x1, v_y, x2, y2)

        self.cache[(x1, y1, x2, y2)] = val
        return val

    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        self.horizontalCut = horizontalCut
        self.verticalCut = verticalCut
        self.cache = dict()
        return self.minimumCostRect(0, 0, m, n)
16800