<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)
        m = len(grid[0]) if n else 0

        # Collect all positions of '1's
        ones = []
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    ones.append((i, j))
        total_ones = len(ones)
        if total_ones == 0:
            return 0  # No '1's to cover

        # Helper function to find the minimal bounding rectangle in a region
        def get_min_rectangle(r_start, r_end, c_start, c_end):
            min_r, max_r = n, -1
            min_c, max_c = m, -1
            for i in range(r_start, r_end):
                for j in range(c_start, c_end):
                    if grid[i][j] == 1:
                        if i < min_r:
                            min_r = i
                        if i > max_r:
                            max_r = i
                        if j < min_c:
                            min_c = j
                        if j > max_c:
                            max_c = j
            if min_r > max_r or min_c > max_c:
                return None  # No '1's in this region
            return (min_r, min_c, max_r, max_c)

        min_total_area = float('inf')

        # 1. All Horizontal Splits
        for r1 in range(1, n - 1):
            for r2 in range(r1 + 1, n):
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, r1)
                rect1 = get_min_rectangle(0, r1, 0, m)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [r1, r2)
                rect2 = get_min_rectangle(r1, r2, 0, m)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [r2, n)
                rect3 = get_min_rectangle(r2, n, 0, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

        # 2. All Vertical Splits
        for c1 in range(1, m - 1):
            for c2 in range(c1 + 1, m):
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, c1)
                rect1 = get_min_rectangle(0, n, 0, c1)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [c1, c2)
                rect2 = get_min_rectangle(0, n, c1, c2)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [c2, m)
                rect3 = get_min_rectangle(0, n, c2, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

        # 3. Horizontal then Vertical Splits
        for r in range(1, n):
            for c in range(1, m):
                # Option 3a: Split upper part vertically
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, r) x [0, c)
                rect1 = get_min_rectangle(0, r, 0, c)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [0, r) x [c, m)
                rect2 = get_min_rectangle(0, r, c, m)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [r, n) x [0, m)
                rect3 = get_min_rectangle(r, n, 0, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

                # Option 3b: Split lower part vertically
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, r) x [0, m)
                rect1 = get_min_rectangle(0, r, 0, m)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [r, n) x [0, c)
                rect2 = get_min_rectangle(r, n, 0, c)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [r, n) x [c, m)
                rect3 = get_min_rectangle(r, n, c, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

        # 4. Vertical then Horizontal Splits
        for c in range(1, m):
            for r in range(1, n):
                # Option 4a: Split left part horizontally
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, r) x [0, c)
                rect1 = get_min_rectangle(0, r, 0, c)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [r, n) x [0, c)
                rect2 = get_min_rectangle(r, n, 0, c)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [0, n) x [c, m)
                rect3 = get_min_rectangle(0, n, c, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

                # Option 4b: Split right part horizontally
                rects = []
                valid = True
                total_covered = 0
                # Region 1: [0, n) x [0, c)
                rect1 = get_min_rectangle(0, n, 0, c)
                if rect1:
                    area1 = (rect1[2] - rect1[0] + 1) * (rect1[3] - rect1[1] + 1)
                    rects.append((rect1, area1))
                    total_covered += sum(1 for pos in ones if rect1[0] <= pos[0] <= rect1[2] and rect1[1] <= pos[1] <= rect1[3])
                else:
                    valid = False
                # Region 2: [0, r) x [c, m)
                rect2 = get_min_rectangle(0, r, c, m)
                if rect2:
                    area2 = (rect2[2] - rect2[0] + 1) * (rect2[3] - rect2[1] + 1)
                    rects.append((rect2, area2))
                    total_covered += sum(1 for pos in ones if rect2[0] <= pos[0] <= rect2[2] and rect2[1] <= pos[1] <= rect2[3])
                else:
                    valid = False
                # Region 3: [r, n) x [c, m)
                rect3 = get_min_rectangle(r, n, c, m)
                if rect3:
                    area3 = (rect3[2] - rect3[0] + 1) * (rect3[3] - rect3[1] + 1)
                    rects.append((rect3, area3))
                    total_covered += sum(1 for pos in ones if rect3[0] <= pos[0] <= rect3[2] and rect3[1] <= pos[1] <= rect3[3])
                else:
                    valid = False
                if valid and total_covered == total_ones:
                    total_area = sum(area for _, area in rects)
                    if total_area < min_total_area:
                        min_total_area = total_area

        if min_total_area == float('inf'):
            return -1  # No valid partition found

        return min_total_area
3791