<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:
        board_summary = []
        for col in range(len(board[0])):
            pq = []
            # first three largest vals and its row index
            for row in range(len(board)):
                heapq.heappush(pq, (board[row][col], row))

                if len(pq) > 3:
                    heapq.heappop(pq)
            
            # add three into summary
            # pq.sort(reverse=True)
            board_summary.append(pq)
        
        return self.dp(board_summary, 0, ['0']*len(board), 0, {})
    
    def dp(self, board_summary, col, row_used, used_count, memo):
        n = len(board_summary)
        if used_count == 3:
            return 0
        
        if col >= n:
            return float("-inf")
        
        key = (col, "-".join(row_used))
        if key in memo:
            return memo[key]
        
        res = self.dp(board_summary, col+1, row_used, used_count, memo)
        for i in range(3):
            val, row_index = board_summary[col][i]
            # if the row is already used
            if row_used[row_index] == "1":
                continue
            
            row_used[row_index] = "1"
            used_count += 1

            next_dp = self.dp(board_summary, col+1, row_used, used_count, memo)
            if next_dp != float("-inf"):
                res = max(res, next_dp + val)
            
            row_used[row_index] = "0"
            used_count -= 1

        memo[key] = res
        return res



107501