题目描述

淘淘蓝蓝在打游戏。他们有 $n$ 个技能，每个技能有 $a_i$，$b_i$ 两个正整数为参数，分别表示法术加成与基础伤害。具体的，如果他们的法术强度为 $k$，则该技能造成的伤害为 $a_i \cdot k + b_i$。

由于他们技能的基础伤害不是很高，在最后与 boss 的对战中，淘淘蓝蓝使用了外挂，大幅提升了自己的法术强度。淘淘蓝蓝有 $q$ 个询问，每个询问有两个参数 $k$ 和 $m$，表示当前的法术强度为 $k$，最多能使用 $m$ 个技能，他们想知道这 $m$ 个技能最多能打出多少伤害。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $a_i$，$b_i$，表示第 $i$ 个技能的法术加成与基础伤害。

第 $n+2$ 行，一个整数 $q$，表示有 $q$ 个询问。

接下来 $q$ 行，每行两个整数 $k$ 和 $m$，表示当前的法术强度为 $k$，最多能使用 $m$ 个技能。

输出格式

$q$ 行，每行一个整数，为伤害的最大值。

输入样例

4
1007 991
514 8
3134 62
559 101
1
2103 3

输出样例

9885254

数据范围

• 对于 20% 的数据，$n, q \leq 100$
• 对于 40% 的数据，$n, q \leq 1000$
• 对于 60% 的数据，$n, q \leq 5000$
• 对于 80% 的数据，$n, q \leq 100000, m \leq 500$
• 对于 100% 的数据，$1 \leq n, q \leq 500000$, $1 \leq a_i \leq 10000$, $1 \leq b_i \leq 1000$, $1000 \leq k \leq 100000000$, $1 \leq m \leq n$;