<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;= 10<sup>5</sup></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 minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        # have to cut every edge at least once, but can decide whether to cut pre or post horiz/vert cut
        # need to do it in O(n)
        # [2,5] and [3,4]
            # x 3 y 4 z
            #     2
            # x 3 y 4 z
            #     5
            # x 3 y 4 z
            # probably should cut 5 first, then 3 and 4 on 2 segments, then two 2's?
                # 5 + 3*2 + 4*2 + 2*3 -> 25
                # vs eg 5 + 2 + 3*3+4*3
        # should I always cut the biggest edge?
            # cost of cutting horiz edge x (for a subgrid), w n vert edges
                # x + n*(sum(vert))
                    # 3 + 5 + min(4*2+5, 5*2+4) -> 3 + 5*2 + 4*2
                                            # or.  3 + 4 + 5*3
                    # 5 + 3 + 4 + 3 + 4 -> 5 + 3*2 + 4*2
                    # 5 + 2*(sum(vert)) -> n^2 + 1 - 2n=1+n(n-2)
                    # 3 + 5*2 + 4*2
                    # sum(vert) + 5*n
                        # 3+4+5*3
                        # 4+3+5*3
                        # 4 + 5*2 + 3*2
                        # always 5 total cuts, so just deciding which one to cut once vs cutting multiple times
                # 3x2 -> 5 cuts (n*m-1)
                # 3x3 -> 8 cuts (n*m-1)
                # vs sum(vert) + (n-1)*x
        # take the max cut (say vert)
        # now we just optimize for the 2 segments
            # seg 1: horiz + vert[:i] -> take max(?)
            # seg 2: horiz + vert[i+1:] -> take max(?)
                # but, the # of cuts depends on the segment's state...
                    # will eventually get to n/2 segments
                # next cut: if horiz is best, then we cut that horiz on both segments -> now have vert=2, horiz=2
                    # if vert is best, we cut 1 seg on that vert, now have vert=3
                # next cut: if h best, cut horiz on both vert segments (2), now have vert=2 horiz=3
                    # if v is best, cut vert on the 2 relevant horiz segments (2), now have vert=3 horiz=2
            # tricky part is if different segments have a diff ordering...
                # but maybe it's not possible
            # how to partition a sort though?
                # need sorted(vert[:i]) / heap(vert[:i])
        heaph = [-x for x in horizontalCut]
        heapify(heaph)
        nvert = 1
        heapv = [-x for x in verticalCut]
        heapify(heapv)
        nhoriz = 1
        cost = 0
        # for _ in range(m*n - 1):
        while heaph or heapv:
            # heapv[0]*nhoriz vs heaph[0]*nvert
                # next round will be:
                    # v*nh + h*(nv+1) = vx + hy + h
                    # h*nv + v*(nh+1) = hy + vx + v -> diff is h-v -> so better option is always the small val, regardless of x and y
                    # v*nh + v2*nh + h*(nv+2) -> vx + v2x + hy + 2h
                    # h*nv + v*(nh+1) + v2*(nh+1) -> hy + vx + v + v2x + v2
                    # vx + h(y+1) + v2(x+1) -> vx + hy + h + v2x + v2
                        # options are:
                            # 2h
                            # v+v2
                            # h+v2
                        # if v+v2 < 2h, should have picked that, but that implies v<h (cuz v2>v) so already would have
                        # h+v2 < 2h, -> v2<h
                    # 
            if not heaph or (heapv and heapv[0] < heaph[0]):
                best = -heappop(heapv)
                cost += best*nhoriz
                nvert += 1
            else:
                best = -heappop(heaph)
                cost += best*nvert
                nhoriz += 1

        return cost

35800