<p>You are given a 2D matrix <code>grid</code> consisting of positive integers.</p>

<p>You have to select <em>one or more</em> cells from the matrix such that the following conditions are satisfied:</p>

<ul>
	<li>No two selected cells are in the <strong>same</strong> row of the matrix.</li>
	<li>The values in the set of selected cells are <strong>unique</strong>.</li>
</ul>

<p>Your score will be the <strong>sum</strong> of the values of the selected cells.</p>

<p>Return the <strong>maximum</strong> score you can achieve.</p>

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

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

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

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid1drawio.png" /></p>

<p>We can select the cells with values 1, 3, and 4 that are colored above.</p>
</div>

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

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

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

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid8_8drawio.png" style="width: 170px; height: 114px;" /></p>

<p>We can select the cells with values 7 and 8 that are colored above.</p>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 100</code></li>
</ul>

# class Solution:
#     def maxScore(self, grid: List[List[int]]) -> int:


#         m = len(grid)
#         n = len(grid[0])
        
#         newgrid = [[] for _ in range(m)]
#         vis = [[] for _ in range(101)]
#         for i in range(m):
#             newgrid[i] = sorted(grid[i],reverse=True)
#         print(newgrid)
#         vis1 = [0 for _ in range(101)]
        

#         dp = [[-1 for _ in range(2**10+1)] for _ in range(m)]
#         def rec(i,cur):
#             if(i==m):
#                 return 0
            
#             if(dp[i][cur]!=-1):
#                 return dp[i][cur]
            
#             maxx = 0
#             for j in range(n):
#                 if(vis1[newgrid[i][j]]==0):
#                     vis1[newgrid[i][j]]=1
#                     maxx = max(maxx,newgrid[i][j]+rec(i+1,cur | 1<<j))
#                     vis1[newgrid[i][j]]=0
                
#             maxx = max(maxx,rec(i+1,cur))
#             dp[i][cur] = maxx
#             return maxx
            
#         rec(0,0)
#         # print(dp)
#         return dp[0][0]


class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:


        m = len(grid)
        print(m)
        n = len(grid[0])
        newgrid = [[] for _ in range(m)]
        vis = [[] for _ in range(101)]
        for i in range(m):
            newgrid[i] = sorted(grid[i],reverse=True)
        # print(newgrid)
        self.sol = 0
        for i in range(m):
            for j in range(n):
                vis[grid[i][j]].append(i)

        # print(vis[:10])
        vis1 = [0 for _ in range(101)]
        k = m
        for i in range(100,-1,-1):
            vis[i] = list(set(vis[i]))

        dp = [[-1 for _ in range(2**10+1)] for _ in range(101)]
        def rec(val,cur):
            
            if(val==0):
                return 0
            # print(vis[val])
            if(dp[val][cur]!=-1):
                return dp[val][cur]
            maxx = 0
            if(vis[val]):
                for idx in vis[val]:
                    if(cur & 1<<idx==0):
                        # vis1[idx] = 1
                        maxx = max(maxx,val+rec(val-1,cur | 1<<idx))
                        # vis1[idx] = 0
                    else:
                        maxx = max(maxx,rec(val-1,cur))
            else:
                maxx = max(maxx,rec(val-1,cur))
            dp[val][cur] = maxx
            return maxx
        rec(100,0)
        # print(dp)
        return dp[100][0]

        

        
34800