Migrated from Lutece 2999 吃什么好呢

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大学生经常在想今天该吃什么，这令他们十分苦恼，现在他们将问题抛给了你。

有 $n$ 位大学生，出于奇怪的原因，给他们的选择只有两种：盒饭 $A$ 和盒饭 $B$。第 $i$ 位大学生吃到盒饭 $A$ 会得到 $a_i$ 的幸福度，吃到盒饭 $B$ 会得到 $b_i$ 的幸福度。

你需要到食堂帮他们买饭回来并分配。食堂有 $m$ 个窗口，出于奇怪的原因，每个窗口也恰好售卖这两种盒饭。每个窗口有特定的购买规则，在第 $j$ 个窗口，购买盒饭 $A$ 的份数必须是 $x_j$ 的倍数，购买盒饭 $B$ 的份数必须是 $y_j$ 的倍数。

大学生都很注意健康，所以每个人会吃且只吃一份盒饭；大学生都很勤俭节约，所以你买的所有盒饭都需要分配出去。

你是一只懒狗，所以你只会去一个窗口帮他们买饭并分发给他们。你需要求出在每个窗口，所有的大学生可能得到的幸福度之和最大是多少？如果在这个窗口没有合适的购买方案，输出 -1。

Input

第一行包括一个整数 $n(1 \leq n \leq 3\times10^5)$，代表大学生的数量。

接下来 $n$ 行，第 $i$ 行包括两个整数 $a_i$ 和 $b_i(1 \leq a_i,b_i \leq 10^9)$，含义与题面一致。 接下来一行包括一个整数 $m(1 \leq m \leq 3 \times10^5)$，代表食堂窗口的数量。

接下来 $m$ 行，第 $j$ 行包括两个整数 $x_j$ 和 $y_j(1 \leq x_j,y_j \leq n)$，含义与题面一致。

Output

输出 $m$ 个整数，第 $i$ 行代表在第 $i$ 个窗口买饭可能得到的幸福度之和的最大值。如果在第 $i$ 个窗口没有合适的购买方案，输出-1。

Samples

3
5 10
100 50
2 2
4
2 3
1 1
3 2
2 2

62
112
107
-1

Note

在第一个窗口，只有一种合适的购买方案，即购买三份盒饭 $B$，大学生的幸福度之和为 $10+50+2=62$。

在第二个窗口，一种最优的购买方案是买一份盒饭 $A$ 和两份盒饭 $B$，将盒饭 $A$ 分给第二位大学生，盒饭 $B$ 分给其余两位大学生，此时幸福度之和为 $10+100+2=112$。

在第四个窗口，没有合适的购买方案。

Resources

2023 UESTC ICPC Training for Math