<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;= 500</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 500</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 = len(board)
        n = len(board[0])

        max_threes = []
        for row in board:
            row_with_idx = [(val, i) for i, val in enumerate(row)]
            row_with_idx.sort(reverse = True)
            max_threes.append(row_with_idx[:3])    

        dp = [[[] for _ in range(n)] for _ in range(m)]
        for i in range(n):
            dp[-1][i].append((board[-1][i], i))

        ans = -inf
        for r in range(m - 2, -1, -1):
            for i in range(3):
                val1, c1 = max_threes[r][i]

                tmp = [-inf] * n
                for r2 in range(r + 1, m):
                    for j in range(3):
                        val2, c2 = max_threes[r2][j]

                        if c1 != c2:
                            tmp[c2] = max(tmp[c2], val1 + val2) 

                            if m - r >= 3 and r2 + 1 != m:
                                prev = dp[r2][c2][0][0] if dp[r2][c2][0][1] != c1 else dp[r2][c2][1][0]
                                ans = max(ans, val1 + prev)
                        
                top_three = [-inf] * 3
                for c3 in range(n):
                    if top_three[0] == -inf or tmp[top_three[0]] <= tmp[c3]:
                        top_three[2] = top_three[1]
                        top_three[1] = top_three[0]
                        top_three[0] = c3
                    elif top_three[1] == -inf or tmp[top_three[1]] <= tmp[c3]:
                        top_three[2] = top_three[1] 
                        top_three[1] = c3
                    elif top_three[2] == -inf or tmp[top_three[2]] <= tmp[c3]:
                        top_three[2] = c3
                
                for c4 in top_three:
                    dp[r][c1].append((tmp[c4], c4))

        return ans     
50079