<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:
    best = 0
    def maxScore(self, grid: List[List[int]]) -> int:
        if len(grid) == len(grid[0]) and len(set(tuple(r) for r in grid)) == 1 and len(set(grid[0])) == len(grid[0]):
            return sum(grid[0])
        for i, row in enumerate(grid):
            grid[i] = sorted(set(row), reverse=True)
        
        @cache
        def dfs(cur_indices):
            sorted_indices = cur_indices
            if sum(grid[r][cur_indices[r]] for r in range(len(grid)) if r < len(cur_indices) and cur_indices[r] < len(grid[r])) < self.best:
                return 0

            c = Counter(grid[r][cur_indices[r]] for r in range(min(len(cur_indices), len(grid))) if cur_indices[r] < len(grid[r]))
            max_num = max((k for k, v in c.items() if v > 1), default=-1)
            rows_with_max_num = [r for r in range(len(grid)) if r < len(cur_indices) and cur_indices[r] < len(grid[r]) and grid[r][cur_indices[r]] == max_num]
            # print(max_num, rows_with_max_num)
            if len(rows_with_max_num) <= 1:
                ans = sum(grid[r][cur_indices[r]] for r in range(len(grid)) if r < len(cur_indices) and cur_indices[r] < len(grid[r]))
                self.best = max(self.best, ans)
                return ans
            else:
                best = 0
                for r in rows_with_max_num:
                    cur_indices = cur_indices[:r] + (cur_indices[r]+1,) + cur_indices[r+1:]
                    best = max(best, dfs(cur_indices))
                    cur_indices = cur_indices[:r] + (cur_indices[r]-1,) + cur_indices[r+1:]
                self.best = max(self.best, best)
                return best
            
            
        return dfs(tuple([0]*len(grid)))
30360