The Best Teams

For each of several tournaments, a selector must pick the strongest possible team. There are $N$ players available, and each player has an age and a skill. The strength of a team equals the sum of the skills of its players.

However, two players with similar skills must never be placed on the same team, because they would interfere with each other and fail to collaborate. Two players are said to have similar skills if no other player has a skill value strictly between theirs. Since all skill values are distinct, this is exactly the condition that the two players are adjacent in the list of all $N$ players sorted by skill.

Teams are chosen for $T$ tournaments. Each tournament has two restrictions:

• an age limit $A$: every chosen player must have age at most $A$;
• a size limit $K$: the team may contain at most $K$ players.

Tournaments are independent, so a player may be used in more than one tournament. Note that the adjacency (the similar skills relation) is always defined over the full sorted list of all $N$ players, regardless of which players are eligible for a given tournament.

For each tournament, determine the strength (total skill) of the strongest valid team the selector can assemble.

The first line contains an integer $N$ — the number of players.

Each of the next $N$ lines contains two space-separated integers $\text{Age}_i$ and $\text{Skill}_i$ — the age and skill of the $i$-th player.

The next line contains an integer $T$ — the number of tournaments.

Each of the next $T$ lines contains two integers $A_i$ and $K_i$ — the age limit and the team-size limit of the $i$-th tournament.

For each tournament, print a single integer on its own line: the strength (total skill) of the strongest valid team, in the same order as the tournaments are given.

If no player can be selected, print 0. Use a 64-bit integer type, since the answer can be large.

• $1 \le N \le 300\,000$
• $1 \le T \le 300\,000$
• $1 \le \text{Age}_i,\ \text{Skill}_i \le 10^9$
• All skill values are distinct.

In the sample, sorting the players by skill gives the order (by input index) $6, 7, 3, 4, 1, 2, 5$. Hence the pairs of players with similar skills — those that cannot share a team — are $(6,7), (7,3), (3,4), (4,1), (1,2), (2,5)$.

• Tournament 1 ($A=20$, $K=3$): the best team is players $\{1, 3, 6\}$ with total skill $21 + 19 + 5 = 45$.
• Tournament 2 ($A=50$, $K=2$): the best team is players $\{1, 5\}$ with total skill $21 + 50 = 71$.
• Tournament 3 ($A=99$, $K=5$): the best team is players $\{1, 3, 5, 6\}$ with total skill $21 + 19 + 50 + 5 = 95$.
• Tournament 4 ($A=10$, $K=2$): every player is older than $10$, so no team can be formed and the answer is $0$.