CF1728E.Red-Black Pepper

Monocarp is going to host a party for his friends. He prepared $n$ dishes and is about to serve them. First, he has to add some powdered pepper to each of them — otherwise, the dishes will be pretty tasteless.

The $i$-th dish has two values $a_i$ and $b_i$ — its tastiness with red pepper added or black pepper added, respectively. Monocarp won't add both peppers to any dish, won't add any pepper multiple times, and won't leave any dish without the pepper added.

Before adding the pepper, Monocarp should first purchase the said pepper in some shop. There are $m$ shops in his local area. The $j$-th of them has packages of red pepper sufficient for $x_j$ servings and packages of black pepper sufficient for $y_j$ servings.

Monocarp goes to exactly one shop, purchases multiple (possibly, zero) packages of each pepper in such a way that each dish will get the pepper added once, and no pepper is left. More formally, if he purchases $x$ red pepper packages and $y$ black pepper packages, then $x$ and $y$ should be non-negative and $x \cdot x_j + y \cdot y_j$ should be equal to $n$.

For each shop, determine the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it's impossible to purchase the packages in the said way, print -1.

Monocarp 将为他的朋友们举办一场聚会。他已准备了 $n$ 道菜肴，正准备上菜。首先，他必须给每道菜添加一些辣椒粉——否则这些菜肴将索然无味。

第 $i$ 道菜有两个数值 $a_i$ 和 $b_i$：分别表示添加红辣椒粉和黑辣椒粉后的美味度。Monocarp 不会向同一道菜同时添加两种辣椒粉，不会对同一道菜重复添加同一种辣椒粉，也不会遗漏任何一道菜而不添加辣椒粉。

在添加辣椒粉之前，Monocarp 必须先到某家商店购买所需辣椒粉。他所在地区共有 $m$ 家商店。第 $j$ 家商店出售两种包装：红辣椒粉每包可供 $x_j$ 份菜肴使用，黑辣椒粉每包可供 $y_j$ 份菜肴使用。

Monocarp 恰好只去一家商店，并在该商店购买若干（可能为零）包红辣椒粉和若干（可能为零）包黑辣椒粉，使得每道菜恰好添加一次辣椒粉，且不剩余任何辣椒粉。更准确地说，若他购买了 $x$ 包红辣椒粉和 $y$ 包黑辣椒粉，则 $x$ 和 $y$ 应为非负整数，且需满足 $x \cdot x_j + y \cdot y_j = n$。

对每家商店，请计算 Monocarp 仅在该商店购买辣椒粉并完成所有菜肴的调味后，所能达到的最大总美味度。若无法按上述方式购买辣椒粉包，请输出 -1。

The first line contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of dishes.

The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) — the tastiness of the $i$-th dish with red pepper added or black pepper added, respectively.

The next line contains a single integer $m$ ($1 \le m \le 3 \cdot 10^5$) — the number of shops.

The $j$-th of the next $m$ lines contains two integers $x_j$ and $y_j$ ($1 \le x_j, y_j \le n$) — the number of servings the red and the black pepper packages are sufficient for in the $j$-th shop, respectively.

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 表示菜肴的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$）—— 分别表示第 $i$ 道菜肴添加红椒或黑椒后的美味度。

下一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）—— 表示商店的数量。

接下来的 $m$ 行中，第 $j$ 行包含两个整数 $x_j$ 和 $y_j$（$1 \le x_j, y_j \le n$）—— 分别表示第 $j$ 家商店中红椒包和黑椒包各自足以供应的份数。

Print $m$ integers. For each shop, print the maximum total tastiness of the dishes after Monocarp buys pepper packages only in this shop and adds the pepper to the dishes. If it's impossible to purchase the packages so that each dish will get the pepper added once and no pepper is left, print -1.

输出 $m$ 个整数。对于每家商店，输出 Monocarp 仅在该商店购买胡椒包，并将胡椒添加到菜肴中后，所有菜肴的总美味度的最大值。如果无法购买胡椒包，使得每道菜恰好添加一次胡椒且没有胡椒剩余，则输出 -1。

Consider the first example.

In the first shop, Monocarp can only buy $0$ red pepper packages and $1$ black pepper package. Black pepper added to all dishes will sum up to $10 + 50 + 2 = 62$.

In the second shop, Monocarp can buy any number of red and black pepper packages: $0$ and $3$, $1$ and $2$, $2$ and $1$ or $3$ and $0$. The optimal choice turns out to be either $1$ and $2$ or $2$ and $1$. Monocarp can add black pepper to the first dish, red pepper to the second dish and any pepper to the third dish, the total is $10 + 100 + 2 = 112$.

In the third shop, Monocarp can only buy $1$ red pepper package and $0$ black pepper packages. Red pepper added to all dishes will sum up to $5 + 100 + 2 = 107$.

In the fourth shop, Monocarp can only buy an even total number of packages. Since $n$ is odd, it's impossible to get exactly $n$ packages. Thus, the answer is $-1$.

考虑第一个例子。

在第一家商店中，Monocarp 只能购买 $0$ 包红胡椒和 $1$ 包黑胡椒。将黑胡椒添加到所有菜肴中，总和为 $10 + 50 + 2 = 62$。

在第二家商店中，Monocarp 可以购买任意数量的红胡椒包和黑胡椒包：$(0,3)$、$(1,2)$、$(2,1)$ 或 $(3,0)$。最优选择为 $(1,2)$ 或 $(2,1)$。Monocarp 可将黑胡椒加入第一道菜，红胡椒加入第二道菜，并将任意一种胡椒加入第三道菜，总和为 $10 + 100 + 2 = 112$。

在第三家商店中，Monocarp 只能购买 $1$ 包红胡椒和 $0$ 包黑胡椒。将红胡椒添加到所有菜肴中，总和为 $5 + 100 + 2 = 107$。

在第四家商店中，Monocarp 只能购买总数为偶数的胡椒包。由于 $n$ 是奇数，因此无法恰好获得 $n$ 包胡椒。故答案为 $-1$。