Best first
Intuition\nWe can reduce our time-complexity by best-first search approach.\nTo find the best, we sort all the rows in non-increasing order.\n\n# Approach\nNow 
# Intuition\nWe can reduce our time-complexity by best-first search approach.\nTo find the best, we sort all the rows in non-increasing order.\n\n# Approach\nNow in an recursive manner we explore the biggest value in each row at first. With that we can quickly get the best result.\n\nWe can compare with existing best to prune a branch that is not optimal.\n\n```\nprediction = calc(row+1,mask,presum)\nret = prediction\nfor x in grid[row]:\n    if (1<<x) & mask:\n        continue\n        \n    if (x+prediction) <= ret: # prune\n        continue\n\n```\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        \n        NROW = len(grid)\n        NCOL = len(grid[0])\n        \n        for row in grid:\n            row.sort(reverse=True)\n        \n        @cache\n        def calc(row,mask,presum):\n            if row == NROW:\n                return presum\n                \n            prd = calc(row+1,mask,presum)\n            ret = prd\n            for x in grid[row]:\n                if (1<<x) & mask:\n                    continue\n                    \n                if (x+prd) <= ret:\n                    continue\n                ret = max(ret, calc(row+1,mask | (1<<x), presum+x))\n                \n            return ret\n    \n        result = calc(0,0,0)\n        return result\n```
['Python3']