<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:
        '''
        * every horizontal and vertical cut has a cost (given)
        * use all cuts.. and break the cake into 1 * 1 pieces.. 
        ====
        * try every cut? => at most 10**3 cuts.. 
        * cuts can be in any order as long it's the minimum total cost..
        * cut cost never changes.. 
        * So, it's better to use a lower cost cut to break into multiple pices.. 
        * and to use the high cost cuts to break it into two.. 
        * I can do this: make all the high cost cuts first.. that way I do less of high cost cut.. and then use all the smaller cost cuts to break into 1 x 1

            * this also seems to work for example: 
                h_cuts = [1, 3]; v_cuts = [5]
                vertical cut is the highest costing cut.. so use it first.. 
                now I have two 3 x 1 pieces.. 
                then use h_cuts[1] to break each 3 x 1 into 1 x 1 pices.. 
                then use h_cuts[0] to break each 3 x 1 into 1 x 1 pices..  
            ==> WORKS! sorting with highest cut to lowest cut.. that ways use small costs more at later state when breaking into many chunks till everything becomes 1 * 1
        '''

        horizontal_costs = sorted(horizontalCut)
        vertical_costs = sorted(verticalCut)

        every_h_cut = sum(horizontal_costs) # cut across top to bottom fully..
        every_v_cut = sum(vertical_costs)  # cut across left to right fully.. 

        ans = 0

        while horizontal_costs and vertical_costs: # when both horizontal and vertical cuts are available.. I need to compare and check which is the highest and use it first..
            if horizontal_costs[-1] > vertical_costs[-1]: 
                ans += horizontal_costs[-1] + every_v_cut # cut horizontall first (since it costs more..).. then the piece across top to bottom.. (using all verical cuts that is not yet explicitly used..ie., popped)
                every_h_cut -= horizontal_costs.pop() # update hcuts: remove this used cut.. and also remove it from across horizontal cuts since it was just made.. 
            else: 
                ans += vertical_costs[-1] + every_h_cut # cut vertically first (since it costs more..).. then the piece across left to right.. (using all horizontal cuts that is not yet explicitly used.. ie.,popped)
                every_v_cut -= vertical_costs.pop() # update vcuts: remove this used cut.. and also remove it from across vertical cuts since it was just made.. 

        if horizontal_costs: 
            ans += every_h_cut # remaining h cuts if remaining
        if vertical_costs:
            ans += every_v_cut # remaining v cuts if remaining
        
        return ans
33900