<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:
        res = -inf
        def backtrack(row, selected, current_sum):
            # If we are at the end of the grid, return the current sum
            if row == len(grid):
                nonlocal res
                res = max(res, current_sum)
                return
            # take nothing
            backtrack(row+1, selected, current_sum)
            for value in sorted(grid[row], reverse=True):
                if value not in selected:
                    max_score = backtrack(row + 1, selected | {value}, current_sum + value)
    
        backtrack(0, set(), 0)
        return res

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        for i in range(n):
            grid[i].sort(reverse=True)
        
        res = -float('inf')
        max_possible = list(accumulate([max(row) for row in grid][::-1]))[::-1]

        def backtrack(row, selected, current_sum):
            nonlocal res
            if row == n:
                res = max(res, current_sum)
                return
            
            if current_sum + max_possible[row] < res:
                return
            
            backtrack(row+1, selected, current_sum)
            for value in grid[row]:
                if not (selected & (1 << value)):
                    backtrack(row + 1, selected | (1 << value), current_sum + value)
        
        backtrack(0, 0, 0)
        return res

# class Solution:
#     def maxScore(self, grid: List[List[int]]) -> int:
#         n = len(grid)
#         m = len(grid[0])
        
#         # for i in range(n):
#         #     grid[i].sort(reverse=True)
        
#         # max_possible = list(accumulate([max(row) for row in grid][::-1]))[::-1]

#         @cache
#         def dp(row, selected):
#             if row == n:
#                 return 0
            
#             res = dp(row+1, selected)
#             for value in grid[row]:
#                 if not (selected & (1 << value)):
#                     res = max(res, value + dp(row + 1, selected | (1 << value)))
#             return res
        
#         return dp(0,0)



import numpy
import scipy
class Solution:
    # def maxScore(self, grid: List[List[int]]) -> int:
        
        
# [Python] Hungarian, 5 lines
# 12
# lee215's avatar
# lee215
# 212270
# Last Edit: a day ago

# 929 VIEWS

# Hungarian problem.

# Time O(100^3)
# Space O(100^2)


# Python

    def maxScore(self, grid: List[List[int]]) -> int:
        A = numpy.array([[0] * 101 for r in grid])
        for i,r in enumerate(grid):
            for a in r:
                A[i][a] = -a
        return int(-A[scipy.optimize.linear_sum_assignment(A)].sum())
    
# tusov8899

# 75
# Last Edit: a day ago

# Read More
# Thank you the the amazing solution!
# We can simplify the code as below

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        @cache
        def f(val, seen):
            if val == mx_val: return 0

            # Skip val
            ret = f(val + 1, seen)

            # Take val
            for ridx in val2ridx[val]:
                if (1 << ridx) & seen == 0:
                    ret = max(ret, val + f(val + 1, seen | (1 << ridx)))
            
            return ret

        mx_val = 101
        val2ridx = [set() for _ in range(mx_val)]
        for ridx, row in enumerate(grid):
            for val in row:
                val2ridx[val].add(ridx)
        
        return f(1, 0)
    
    
    # my version
    # IDEA: standard O(m*n*2^{100}) bitmask dp is way too slow.
    # reverse the bitmask. instead of it being the values, make it the number of rows!!! just remember which rows we have previously used. instead of iterating through rows and choosing values,
    # we iterate over the values themselves, and then try all different rows we can use this value from
    
    # think about the final optimal solution: it is a set of values, from various rows. REVERS THE PROBLEM. instead of row -> value, think value -> row!
    
    # now very fast: just O(100 * 2^10)
    def maxScore(self, grid: List[List[int]]) -> int:
        m,n = len(grid), len(grid[0])
        val_idx = defaultdict(list) # THIS CAN BE A SET!!! OPTIMIZE. 
        for i in range(m):
            for v in grid[i]:
                val_idx[v].append(i)
        
        # can sort the val_idx map, in case of sparse keys in the map...
        max_val = max(max(row) for row in grid)
        @cache
        def dp(val, bitmask):
            if val > max_val: return 0
            
            # skip using val
            res = dp(val+1, bitmask)
            
            # use val
            # try all row indexs to choose from
            for i in val_idx[val]:
                if bitmask & (1 << i) == 0:
                    res = max(res, val + dp(val+1, bitmask | (1 << i)))
            return res
        
        return dp(0, 0)
    
    # instead of val: optimize to like 'idx in map'
    # i think this is like the actual fastest.
    def maxScore(self, grid: List[List[int]]) -> int:
        m,n = len(grid), len(grid[0])
        val_idx = defaultdict(set)
        for i in range(m):
            for v in grid[i]:
                val_idx[v].add(i)
        
        l = list(val_idx.items()) # optimize. condense the map
        #print(l)
        #l.sort() # INTERESTING... sorting is actually redundant...
        @cache
        def dp(i, bitmask):
            if i == len(l): return 0
            
            # skip using val
            res = dp(i+1, bitmask)
            
            # use val
            # try all row indexs to choose from
            for j in l[i][1]:
                if bitmask & (1 << j) == 0:
                    res = max(res, l[i][0] + dp(i+1, bitmask | (1 << j)))
            return res
        
        return dp(0, 0)
                
                
            
        
        
        
        
        
        
        
        
        
        
        
        
    
    
92520