<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, g: List[List[int]]) -> int:
        
#         @cache
#         def one(a, b, c, d):
#             # same as problem 3195, just take the minimum x, y and
#             # maximum x, y among all ones and calculate the final area.
#             ar, br, ac, bc = inf, -inf, inf, -inf
#             for i in range(a, b+1):
#                 for j in range(c, d+1):
#                     if g[i][j]:
#                         ar = min(ar, i)
#                         br = max(br, i)
#                         ac = min(ac, j)
#                         bc = max(bc, j)
#             if ar == inf:
#                 return 1
#             return (br - ar + 1) * (bc - ac + 1)

#         @cache
#         def two(a, b, c, d):
#             ans = float(inf)
#             # cut horizontally
#             for i in range(b):
#                 ans = min(one(a, i, c, d) + one(i + 1, b, c, d), ans)
#             # cut vertically
#             for j in range(d):
#                 ans = min(one(a, b, c, j) + one(a, b, j + 1, d), ans)
#             return ans
#         @cache
#         def three(a, b, c, d):
#             ans = float(inf)
#             # cut horizontally
#             for i in range(b):
#                 ans = min(one(a, i, c, d) + two(i + 1, b, c, d), ans)
#                 ans = min(two(a, i, c, d) + one(i + 1, b, c, d), ans)
#             # cut vertically
#             for j in range(d):
#                 ans = min(one(a, b, c, j) + two(a, b, j + 1, d), ans)
#                 ans = min(two(a, b, c, j) + one(a, b, j + 1, d), ans)
#             return ans
        
#         return three(0, len(g)-1, 0, len(g[0])-1)
        


class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        def get(a, b, c, d): # inclusive [a, b], [c, d]
            if b < a or d < c:
                return 1e9
            lx, rx, ty, dy = 1e9, -1, 1e9, -1
            for i in range(a, b+1):
                for j in range(c, d+1):
                    if grid[i][j]:
                        lx = min(lx, j)
                        rx = max(rx, j)
                        ty = min(ty, i)
                        dy = max(dy, i)
            return (rx-lx+1) * (dy - ty+1)
        ans = 1e9
        n, m = len(grid), len(grid[0])
        for i in range(n):
            for j in range(m):
                # type 3
                ans = min(ans, get(0, i, 0, m - 1) + get(i+1, n-1, 0, j) + get(i+1, n-1, j+1, m - 1)) 
                # type 2
                ans = min(ans, get(0, i, 0, j) + get(0, i, j+1, m-1) + get(i+1, n-1, 0, m-1))
                # type 5
                ans = min(ans, get(0, n-1, 0, j) + get(0, i, j+1, m-1) + get(i+1, n-1, j+1, m-1))
                # type 6
                ans = min(ans, get(0, n-1, j+1, m-1) + get(0, i, 0, j) + get(i+1, n-1, 0, j))
        # type 1
        for i in range(n):
            for j in range(i, n):
                ans = min(ans, get(0, i, 0, m-1) + get(i+1, j, 0, m-1) + get(j+1, n-1, 0, m-1))
        # type 4
        for i in range(m):
            for j in range(i, m):
                ans = min(ans, get(0, n-1, 0, i) + get(0, n-1, i+1, j) + get(0, n-1, j+1, m-1))
        return ans
5602