<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:
        n, m = len(board), len(board[0])
        

        cords = [[[] for z in range(m)] for i in range(n)]

        def execute(start, end, inc):
            heap = []
            for i, num in enumerate(board[start]):
                if len(heap) < 3:
                    heapq.heappush(heap, [num, i])
                elif num > heap[0][0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, [num, i])
            

            def exec(row, col, arr):
                currCords = []
                for i in range(len(arr)):
                    if arr[i][1] == col:
                        arr.pop(i)
                        break
                
                arr.sort()
                while len(currCords) < 2:
                    currCords.append(arr.pop())
                
                cords[row][col].append(currCords)

            def check(col, num, arr):
                for i, [numTwo, colTwo] in enumerate(arr):
                    if col == colTwo:
                        arr[i] = [max(num, numTwo), col]
                        heapq.heapify(arr)
                        return True
                return False

            for row in range(start + inc, end, inc):
                newHeap = heap[:]
                for col in range(m):
                    num = board[row][col]
                    exec(row, col, heap[:])

                    if not check(col, num, newHeap):
                        if newHeap[0][0] < num:
                            heapq.heappop(newHeap)
                            heapq.heappush(newHeap, [num, col])
                
                heap = newHeap
        

        execute(0, n, 1)
        execute(n - 1, -1, -1)

        
        currMax = float('-inf')


        def getMax(arr):
            
            currMax = float('-inf')

            cordsOne, cordsTwo = arr


            for numOne, colOne in cordsOne:
                for numTwo, colTwo in cordsTwo:
                    if colOne == colTwo: continue
                    currMax = max(currMax, numOne + numTwo)
            return currMax

        for row in range(1, n - 1):
            for col in range(m):
                currMax = max(currMax, board[row][col] + getMax(cords[row][col]))
        return currMax
            
                    

85906