<p>You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the <strong>sum</strong> of scores of all the players in the team.</p>

<p>However, the basketball team is not allowed to have <strong>conflicts</strong>. A <strong>conflict</strong> exists if a younger player has a <strong>strictly higher</strong> score than an older player. A conflict does <strong>not</strong> occur between players of the same age.</p>

<p>Given two lists, <code>scores</code> and <code>ages</code>, where each <code>scores[i]</code> and <code>ages[i]</code> represents the score and age of the <code>i<sup>th</sup></code> player, respectively, return <em>the highest overall score of all possible basketball teams</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> scores = [1,3,5,10,15], ages = [1,2,3,4,5]
<strong>Output:</strong> 34
<strong>Explanation:</strong>&nbsp;You can choose all the players.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> scores = [4,5,6,5], ages = [2,1,2,1]
<strong>Output:</strong> 16
<strong>Explanation:</strong>&nbsp;It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> scores = [1,2,3,5], ages = [8,9,10,1]
<strong>Output:</strong> 6
<strong>Explanation:</strong>&nbsp;It is best to choose the first 3 players. 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= scores.length, ages.length &lt;= 1000</code></li>
	<li><code>scores.length == ages.length</code></li>
	<li><code>1 &lt;= scores[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= ages[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def bestTeamScore2(self, scores: List[int], ages: List[int]) -> int:
        players = sorted(zip(ages,scores))
        print(players)
        n = len(players)
        dp = {}
        def helper(i):
            key = i
            if key in dp:
                return dp[key]

            max_included = players[i][1]
            max_excluded = 0
            for j in range(i+1,n):
                max_included_j, max_excluded_j = helper(j)

                if players[j][0] == players[i][0] or players[j][1] >= players[i][1]:
                    max_included_j += players[i][1]
                    max_included = max(max_included, max_included_j)
                else:
                    max_excluded = max(max_excluded, max_included_j, max_excluded_j)

            result = (max_included, max_excluded)
            dp[key] = result
            return result

        result = helper(0)        
        return max(result)

    def bestTeamScore3(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        players = sorted(zip(ages,scores))
        dp = [(0,0)] * n
        dp[n-1] = (players[n-1][1], 0)
        for i in range(n-2,-1,-1):
            max_included = players[i][1]
            max_excluded = 0
            for j in range(i+1,n):
                max_included_j, max_excluded_j = dp[j]

                if players[j][0] == players[i][0] or players[j][1] >= players[i][1]:
                    max_included = max(max_included, max_included_j + players[i][1])
                else:
                    max_excluded = max(max_excluded, max_included_j, max_excluded_j)
            dp[i] = (max_included, max_excluded)

        return max(dp[0])

    def bestTeamScore2(self, scores: List[int], ages: List[int]) -> int:
        players = sorted(list(zip(ages, scores)))
        n = len(players)
        dp = {}
        def helper(i, prev_i):
            if i == n:
                return 0
            
            key = (i,prev_i)
            if key in dp:
                return dp[key]

            r1 = 0
            if prev_i == -1 or players[prev_i][0] == players[i][0] or players[prev_i][1] <= players[i][1]:
                r1 = helper(i+1, i) + players[i][1]
            
            r2 = helper(i+1, prev_i)

            result = max(r1,r2)
            dp[key] = result
            return result

        result = helper(0,-1)
        del dp
        return result

    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        players = sorted(list(zip(ages, scores)))
        n = len(players)
        dp = [ [ -math.inf for _ in range(n+1) ] for _ in range(n+1) ]
    
        for i in range(n+1):
            dp[n][i] = 0

        for i in range(n-1,-1,-1):
            for prev_i in range(i,-1,-1):
                dp[i][prev_i] = dp[i+1][prev_i]
                if prev_i == 0 or players[prev_i-1][0] == players[i][0] or players[prev_i-1][1] <= players[i][1]:
                    dp[i][prev_i] = max(dp[i][prev_i], dp[i+1][i+1] + players[i][1])

        return dp[0][0]

# 1 3 5 10 15
# 1 2 3  4 5

# 4 5 6 5
# 2 1 2 1

57000