题目背景

你是国家队教练，你要选择一支最佳队伍去参加 BOI 世界杯。

题目描述

你麾下有 $N$ 名球员，编号为 $1\dots N$，第 $i$ 名球员有一个年龄 $age_i$，和技能值 $skill_i$。

一个队伍的优秀程度为技能值之和。尽管如此，你认为把两名技能值相似的球员放在团队中是不行的，他们会产生矛盾。

• 我们称两个球员 $x,y$ 技能值相似，当且仅当不存在第三个球员 $z$ 使得 $skill_x<skill_z<skill_y$。

球队要参加 $T$ 场比赛。每场比赛有一个年龄限制 $A$，这意味着对于参加这场比赛的任意一个球员 $x$ 满足 $age_x\le A$。此外，对于每场比赛还有一个人数限制 $K$，意味着参赛人数 $\le K$。

一个球员可多次参赛。

输入格式

输入的第一行包含一个整数 $N$，代表球员的数量。

接下来的 $N$ 行中的每一行都包含两个空格分隔的整数 $age_i,skill_i$。

下一行包含一个整数 $T$，表示比赛的数量。

接下来 $T$ 行，每行两个整数 $A,K$，分别表示每场比赛的年龄限制和球员人数限制。

输出格式

对于每场比赛，输出你选择的队伍的优秀程度。

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

提示

数据范围：

Subtask#0 为样例。

$1\le N,T\le 3\times 10^5$，$1\le age_i,skill_i\le10^9$。

对于所有 $i\neq j$ 满足 $skill_i\neq skill_j$。

样例解释：

共有 $6$ 对球员技能值相似，分别为 $(6,7)$ $(7,3)$ $(3,4)$ $(4,1)$ $(1,2)$ $(2,5)$。

第一次比赛派出球员 $1,3,6$。

第二次比赛派出球员 $1,5$。

第三次比赛派出球员 $1,3,5,6$。

第四次比赛无法派出球员，因为没有一个球员年龄 $\le10$。