<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:
  LOWER = 0
  UPPER = 10 ** 6 + 1

  def __init__(self):
    self.tree = defaultdict(int)

  def query(self, ql, qh, cl=LOWER, ch=UPPER, index=1):
    # // cl, ch are the range of the current tree node. index is the current tree node index.
    # // ql, qh are the range to be queried.
    if ch < ql or cl > qh:
      return 0
    if ql <= cl and ch <= qh:
      return self.tree[index]

    m = (cl + ch) // 2
    return max(
      self.query(ql, qh, cl, m, 2 * index),
      self.query(ql, qh, m + 1, ch, 2 * index + 1)
    )

  def update_single(self, qp, val, cl=LOWER, ch=UPPER, index=1):
    # // cl, ch are the range of the current tree node. index is the current tree node index.
    # // qp is the query point to be updated.
    if ch < qp or cl > qp:
      return
    if cl == ch:
      self.tree[index] = val
      return

    m = (cl + ch) // 2

    if qp <= m:
      self.update_single(qp, val, cl, m, 2 * index)
    elif m + 1 <= qp:
      # // Note: we use `m+1` instead of `m`. Otherwise we will recurse infinitely.
      self.update_single(qp, val, m + 1, ch, 2 * index + 1)

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

  def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
    ageScorePair = [(ages[i], scores[i]) for i in range(len(scores))]
    # Sort in ascending order of age and then by score.
    ageScorePair.sort()

    max_sum = 0
    for _, score in ageScorePair:
      max_sum_end_num = self.query(Solution.LOWER, score) + score
      max_sum = max(max_sum, max_sum_end_num)
      self.update_single(score, max_sum_end_num)

    return max_sum
18400