<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 SegmentTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (4 * size)

    def update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = max(self.tree[node], value)
            return

        mid = (start + end) // 2
        if index <= mid:
            self.update(2*node, start, mid, index, value)
        else:
            self.update(2*node+1, mid+1, end, index, value)

        self.tree[node] = max(self.tree[2*node], self.tree[2*node+1])

    def query(self, node, start, end, left, right):
        if left > end or right < start:
            return 0
        if left <= start and end <= right:
            return self.tree[node]

        mid = (start + end) // 2
        left_max = self.query(2*node, start, mid, left, right)
        right_max = self.query(2*node+1, mid+1, end, left, right)
        return max(left_max, right_max)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        # Pair ages and scores, and sort by age (then by score if ages are equal)
        players = sorted(zip(ages, scores))
        
        # Find the maximum score to determine the size of our segment tree
        max_score = max(scores)
        
        # Initialize the segment tree
        seg_tree = SegmentTree(max_score + 1)
        
        max_total_score = 0
        
        for age, score in players:
            # Query the maximum score for all players with score <= current score
            max_prev_score = seg_tree.query(1, 0, max_score, 0, score)
            
            # The best score ending at this player is their score plus the best previous compatible score
            curr_best_score = score + max_prev_score
            
            # Update the tree with this new best score
            seg_tree.update(1, 0, max_score, score, curr_best_score)
            
            # Keep track of the overall maximum score
            max_total_score = max(max_total_score, curr_best_score)
        
        return max_total_score
79200