<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, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        mmax=[[] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if len(mmax[i])>=3 and mmax[i][0][0]<grid[i][j]:
                    heappop(mmax[i])
                    heappush(mmax[i],(grid[i][j],j))
                    continue
                if len(mmax[i])<3:heappush(mmax[i],(grid[i][j],j))
        gg=[]
        for i in range(m):
            for val,j in mmax[i]:
                gg.append((val,i,j))
        gg.sort(reverse=True)
        temp=gg.copy()
        gg=[]
        cc=Counter()
        for val,i,j in temp:
            if cc[j]==3: continue
            cc[j]+=1
            gg.append((val,i,j))
            if len(gg)==12: break
        row,col,rev_row,rev_col={},{},{},{}
        r,c=set(),set()
        for _,i,j in gg: r.add(i); c.add(j);
        r,c=sorted(r),sorted(c)
        for i,val in enumerate(r): 
            row[i]=val
            rev_row[val]=i
        for i,val in enumerate(c):
            col[i]=val
            rev_col[val]=i
        # print(mmax)
        # print(rev_row,rev_col)
        @cache
        def dp(idx,mask_r,mask_c):
            res=-sys.maxsize
            if idx==len(gg): 
                cnt1=bin(mask_r)[2:].count("1")
                cnt2=bin(mask_c)[2:].count("1")
                # print(mask_r,mask_c,cnt1,cnt2)
                return 0 if (cnt1==3 and cnt2==3) else -sys.maxsize 
            #ignore
            res=max(res,dp(idx+1,mask_r,mask_c))
            val,ri,ci=gg[idx]
            ir,ic=rev_row[ri],rev_col[ci]
            #check and take
            if (mask_r & (1<<ir))==0 and (mask_c & (1<<ic))==0:
                res=max(res,dp(idx+1,(mask_r | (1<<ir)),(mask_c | (1<<ic)))+val)
            return res
        return dp(0,0,0)
        
            
        
51133