<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:
        n=len(grid)#y
        m=len(grid[0])#x
        def get_area(x1,y1,x2,y2,g):
            n=len(g)#y
            m=len(g[0])#x
            if x1>x2 or y1>y2:
                return 0
            left=m-1
            right=0
            up=n-1
            down=0
            for i in range(x1,x2+1):
                for j in range(y1,y2+1):
                    try:
                        if g[j][i]:
                            left=min(left,i)
                            right=max(right,i)
                            up=min(up,j)
                            down=max(down,j)
                    except:
                        print(i,j,g)
            # print("l",left,"r",right,"u",up,"d",down)
            return (right-left+1)*(down-up+1)


        
        def three_cut(g):
            n=len(g)#y
            m=len(g[0])#x
            res=float('inf')
            for i in range(1,n-1):#y
                for j in range(i+1,n):#x
                    a1=get_area(0,0,m-1,i-1,g)
                    a2=get_area(0,i,m-1,j-1,g)
                    a3=get_area(0,j,m-1,n-1,g)
                    res=min(res,a1+a2+a3)
            return res

        def cross_cut(g):
            n=len(g)#y
            m=len(g[0])#x
            res=float('inf')
            for i in range(1,n):#y
                for j in range(1,m):#x
                    a1=get_area(0,0,j-1,i-1,g)
                    a2=get_area(j,0,m-1,i-1,g)
                    a3=get_area(0,i,m-1,n-1,g)
                    res=min(res,a1+a2+a3)
            return res
        
        def flip(g):
            i=len(g)#y
            j=len(g[0])#x
            new=[[0 for _ in range(i)] for t in range(j)]
            for a in range(i):
                for b in range(j):
                    new[b][i-1-a]=g[a][b]
            return new



        r1=three_cut(grid)
        r2=cross_cut(grid)
        grid=flip(grid)
        r3=cross_cut(grid)
        r6=three_cut(grid)
        grid=flip(grid)
        r4=cross_cut(grid)
        grid=flip(grid)
        r5=cross_cut(grid)
        print('1:',r1,'2:',r2,'3:',r3,'4:',r4,'5:',r5,'6:',r6)
        return min(r1,r2,r3,r4,r5,r6)
        
3982