최고의 팀

여러 대회 각각에 대해 가장 강한 팀을 뽑아야 한다. 사용할 수 있는 선수는 $N$명이며, 각 선수에게는 나이와 실력이 주어진다. 팀의 강함은 그 팀에 속한 모든 선수의 실력의 합과 같다.

단, 실력이 비슷한 두 선수는 같은 팀에 넣을 수 없다. 서로 방해가 되어 제대로 협력하지 못하기 때문이다. 두 선수의 실력이 비슷하다는 것은, 그 둘의 실력 값 사이에 실력이 있는 다른 선수가 존재하지 않는다는 뜻이다. 모든 선수의 실력 값이 서로 다르므로, 이는 곧 두 선수가 전체 $N$명을 실력 순으로 정렬했을 때 서로 이웃함을 의미한다.

팀은 $T$개의 대회에 대해 각각 뽑는다. 각 대회에는 두 가지 제한이 있다.

• 나이 제한 $A$: 뽑는 모든 선수의 나이는 $A$ 이하여야 한다.
• 인원 제한 $K$: 팀의 선수 수는 $K$명 이하여야 한다.

각 대회는 서로 독립적이므로, 한 선수가 여러 대회에 참여할 수 있다. 이웃 관계(실력이 비슷한 관계)는 특정 대회에서 어떤 선수에게 참가 자격이 있는지와 무관하게, 항상 전체 $N$명을 정렬한 목록을 기준으로 정해진다는 점에 유의하라.

각 대회에 대해, 뽑을 수 있는 가장 강한 팀의 강함(실력의 총합)을 구하여라.

첫째 줄에 선수의 수 $N$이 주어진다.

다음 $N$개의 줄에는 각각 두 정수 $\text{Age}_i$와 $\text{Skill}_i$가 공백으로 구분되어 주어지며, 이는 $i$번째 선수의 나이와 실력이다.

그다음 줄에는 대회의 수 $T$가 주어진다.

다음 $T$개의 줄에는 각각 두 정수 $A_i$와 $K_i$가 주어지며, 이는 $i$번째 대회의 나이 제한과 인원 제한이다.

각 대회에 대해, 뽑을 수 있는 가장 강한 팀의 강함(실력의 총합)을 대회가 주어진 순서대로 한 줄에 하나씩 출력한다.

뽑을 수 있는 선수가 하나도 없으면 0을 출력한다. 답이 매우 클 수 있으므로 64비트 정수 자료형을 사용해야 한다.

• $1 \le N \le 300\,000$
• $1 \le T \le 300\,000$
• $1 \le \text{Age}_i,\ \text{Skill}_i \le 10^9$
• 모든 선수의 실력 값은 서로 다르다.

예제에서 선수들을 실력 순으로 정렬하면 (입력 순번 기준으로) $6, 7, 3, 4, 1, 2, 5$의 순서가 된다. 따라서 실력이 비슷하여 같은 팀에 들어갈 수 없는 선수 쌍은 $(6,7), (7,3), (3,4), (4,1), (1,2), (2,5)$이다.

• 1번 대회 ($A=20$, $K=3$): 가장 강한 팀은 선수 $\{1, 3, 6\}$이며 실력의 합은 $21 + 19 + 5 = 45$이다.
• 2번 대회 ($A=50$, $K=2$): 가장 강한 팀은 선수 $\{1, 5\}$이며 실력의 합은 $21 + 50 = 71$이다.
• 3번 대회 ($A=99$, $K=5$): 가장 강한 팀은 선수 $\{1, 3, 5, 6\}$이며 실력의 합은 $21 + 19 + 50 + 5 = 95$이다.
• 4번 대회 ($A=10$, $K=2$): 모든 선수의 나이가 $10$보다 많으므로 팀을 구성할 수 없고, 답은 $0$이다.