Background

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

Problem Description

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<skill_z<skill_y$.

The team will play $T$ matches. Each match has an age limit $A$, which means that for any player $x$ taking part in this match, $age_x \le A$. In addition, each match has a team size limit $K$, meaning the number of participating players $\le K$.

A player may participate multiple times.

Input Format

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.

Output Format

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

7
17 21
24 36
14 19
27 20
21 50
18 5
33 7
4
20 3
50 2
99 5
10 2

45
71
95
0

Hint

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