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

        dp: list[list[set[int]]] = [[set() for _ in range(n)] for _ in range(1 << n)]

        # print(f"dp={dp}")
        for r in range(n):
            grid[r].sort(reverse=True)
            # print(f"r={r}, grid[r][0]={grid[r][0]}")
            dp[1 << r][r].add(grid[r][0])

        # print(f"dp={dp}")

        for mask in range(1 << n):
            for u in range(n):
                if mask & (1 << u):
                    for v in range(n):
                        if not mask & (1 << v):
                            cs: set[int] = dp[mask][u].copy()

                            mx = 0
                            for c in range(m):
                                if grid[v][c] not in cs:
                                    mx = grid[v][c]
                                    break
                            # print(
                            #     f"mask={bin(mask)}, u={u}, v={v}, dp[mask][u]={dp[mask][u]}, mx={mx}"
                            # )
                            cs.add(mx)
                            if sum(dp[mask | (1 << v)][v]) < sum(cs):
                                dp[mask | (1 << v)][v] = cs
        # print(f"dp={dp}")
        ans = 0
        for r in range(n):
            # print(
            #     f"r={r}, sum={sum(dp[(1 << n) - 1][r])}, dp[{(1 << n) - 1}][{r}]={dp[(1 << n) - 1][r]}"
            # )
            ans = max(ans, sum(dp[(1 << n) - 1][r]))
        return ans
20000