<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>

import bisect
from typing import *
from collections import namedtuple
from sortedcontainers import SortedList, SortedDict
from collections import Counter
from math import inf
from math import gcd
from math import factorial
import string
import random
import itertools
from functools import cache
from fractions import Fraction


class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        R = len(grid)
        for i in range(R):
            grid[i].sort()

        @cache
        def f(mask, M):
            if mask == 0:
                return 0
            ans = 0
            cand = []
            for i in range(R):
                if mask & (1 << i):
                    j = bisect.bisect_right(grid[i], M) - 1
                    if j >= 0:
                        if not cand or grid[i][j] >= cand[0][0]:
                            if cand and grid[i][j] > cand[0][0]:
                                cand.clear()
                        cand.append((grid[i][j], i))
            for m, i in cand:
                ans = max(ans, f(mask - (1 << i), m - 1) + m)
            return ans

        ans = f((1 << R) - 1, 100)
        return ans


s = Solution()
print(s.maxScore(grid=[[1, 2, 3], [4, 3, 2], [1, 1, 1]]))
print(s.maxScore(grid=[[8, 7, 6], [8, 3, 2]]))
print(s.maxScore(grid=[[5], [7], [19], [5]]))

24440