<p>You are given a <code>m x n</code> 2D array <code>board</code> representing a chessboard, where <code>board[i][j]</code> represents the <strong>value</strong> of the cell <code>(i, j)</code>.</p>

<p>Rooks in the <strong>same</strong> row or column <strong>attack</strong> each other. You need to place <em>three</em> rooks on the chessboard such that the rooks <strong>do not</strong> <strong>attack</strong> each other.</p>

<p>Return the <strong>maximum</strong> sum of the cell <strong>values</strong> on which the rooks are placed.</p>

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

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

<p><strong>Output:</strong> 4</p>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" /></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 3)</code>, and <code>(2, 1)</code> for a sum of <code>1 + 1 + 2 = 4</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span></p>

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

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

<p>We can place the rooks in the cells <code>(0, 0)</code>, <code>(1, 1)</code>, and <code>(2, 2)</code> for a sum of <code>1 + 5 + 9 = 15</code>.</p>
</div>

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

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

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

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

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 1)</code>, and <code>(2, 0)</code> for a sum of <code>1 + 1 + 1 = 3</code>.</p>
</div>

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

<ul>
	<li><code>3 &lt;= m == board.length &lt;= 100</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 100</code></li>
	<li><code>-10<sup>9</sup> &lt;= board[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m, n = len(board), len(board[0])
        heap = [(-board[i][j], i, j) for i in range(0, m) for j in range(0, n)]
        heapq.heapify(heap)

        cells = []
        while len(cells) < max(m, n) * 3 or (heap and -cells[-1][0] == heap[0][0]):
            nv, i, j = heapq.heappop(heap)
            cells.append((-nv, i, j))
        size = len(cells)

        def search_1(current: int, skipped_0: int, skipped_1: int) -> int:
            _, i0, j0 = cells[skipped_0]
            _, i1, j1 = cells[skipped_1]
            for i in range(current, size):
                v, ic, jc = cells[i]
                if ic != i0 and jc != j0 and ic != i1 and jc != j1:
                    return v
            return -math.inf

        @functools.cache
        def search_2(current: int, skipped_0: int) -> int:
            if current >= size - 1:
                return -math.inf
            v, ic, jc = cells[current]
            _, i0, j0 = cells[skipped_0]
            if ic == i0 or jc == j0:
                return search_2(current + 1, skipped_0)
            return max(
                v + search_1(current + 1, skipped_0, current),
                search_2(current + 1, skipped_0),
            )

        def search_3(current: int) -> int:
            if current >= size - 2:
                return -math.inf
            v, ic, jc = cells[current]
            return v + search_2(current + 1, current)

        return max(search_3(i) for i in range(0, min(m, n) + 1))

55290