<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1],[1,1,1]]</span></p>

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

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1,0],[0,1,0,1]]</span></p>

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

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there are at least three 1&#39;s in <code>grid</code>.</li>
</ul>

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:

        
        
        output = 10**20
        
        for _ in range(4):
            
            grid = [list(row) for row in zip(*grid[::-1])]
            N,M = len(grid), len(grid[0])
            
            # @cache
            def check_top(v_mini,v_maxi,h_mini,h_maxi):
                grid_cur = [row[h_mini:h_maxi] for row in grid[v_mini:v_maxi]]
                if not grid_cur or not grid_cur[0]:
                    return 0
                def check(g):
                    bot = 0
                    top = len(g)-1
                    while sum(g[bot]) == 0:
                        bot += 1
                        if bot == len(g):
                            return 0
                    while sum(g[top]) == 0:
                        top -= 1
                    return top-bot+1

                return check([list(row) for row in grid_cur]) * check([list(row) for row in list(zip(*grid_cur))])
            
            for y in range(1,N+1):
                for x in range(1,M+1):
                    checking = check_top(0,y,0,x) + check_top(0,y,x,M) + check_top(y,N,0,M)
                    if checking < output:
                        output = checking
                    checking3 = check_top(0,y,0,x) + check_top(y,N,0,x) + check_top(0,N,x,M)
                    if checking3 < output:
                        output = checking3
                    if y == N:
                        for xx in range(x,M+1):
                            checking = check_top(0,N,0,x) + check_top(0,N,x,xx) + check_top(0,N,xx,M)
                            output = min(output, checking)
        
        return output
3410