P8065 [BalkanOI 2012] The Best Teams

You are the national team coach, and you need to choose the best team to take part in the BOI World Cup.

You have $N$ players, numbered $1 \dots N$. Player $i$ has an age $age_i$ and a skill value $skill_i$. The quality of a team is the sum of the skill values. However, you believe it is not acceptable to put two players with similar skill values in the same team, because they will cause conflicts. - We say that two players $x,y$ have similar skill values if and only if there does not exist a third player $z$ such that $skill_x

The first line contains an integer $N$, representing the number of players. Each of the next $N$ lines contains two space-separated integers $age_i, skill_i$. The next line contains an integer $T$, representing the number of matches. Each of the next $T$ lines contains two integers $A, K$, representing the age limit and the team size limit for each match.

For each match, output the quality of the team you choose.

#### Constraints Subtask #0 is the sample. $1 \le N, T \le 3 \times 10^5$, $1 \le age_i, skill_i \le 10^9$. For all $i \ne j$, we have $skill_i \ne skill_j$. #### Sample Explanation There are $6$ pairs of players with similar skill values: $(6,7)$, $(7,3)$, $(3,4)$, $(4,1)$, $(1,2)$, $(2,5)$. In the first match, players $1,3,6$ are selected. In the second match, players $1,5$ are selected. In the third match, players $1,3,5,6$ are selected. In the fourth match, no players can be selected, because there is no player with age $\le 10$. Translated by ChatGPT 5