Red-Black Pepper
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 2300
Tags: brute force, data structures, greedy, math, number theory

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
5 10
100 50
2 2
4
2 3
1 1
3 2
2 2

Example output:
62
112
107
-1

Example input:
10
3 1
2 3
1 1
2 1
6 3
1 4
4 3
1 3
5 3
5 4
10
8 10
9 3
1 4
2 5
8 3
3 5
1 6
7 2
6 7
3 1

Example output:
26
-1
36
30
-1
26
34
26
-1
36

Editorial:
Let's start by learning how to answer a query $$$(1, 1)$$$ — all red pepper and black pepper options are available.
Let's iterate over all options to put the peppers and choose the maximum of them. First, let's use the red pepper for all dishes. Now we want to select some $$$k$$$ of them to use black pepper instead of red pepper. Which ones do we choose? When we switch from the red pepper to the black pepper, the total tastiness changes by $$$-a_i + b_i$$$ for the $$$i$$$-th dish. They are completely independent of each other, so we want to choose $$$k$$$ largest of these values.
Let $$$d_1, d_2, \dots, d_n$$$ be the sequence of values of $$$-a_i + b_i$$$ in a non-increasing order.
Thus, $$$k$$$ black peppers will yield the result of $$$\sum \limits_{i=1}^{n} a_i + \sum \limits_{i=1}^{k} d_i$$$. We can answer a query $$$(1, 1)$$$ by looking for a maximum in the sequence.
Now consider an arbitrary query. Let $$$p_1, p_2, \dots, p_t$$$ be all options for the amount of available black peppers for the query. Naively, we could iterate over all of them and choose the maximum one.
However, notice an interesting thing about the sequence of the answers. By definition, it is non-strictly convex. In particular, one idea that can be extracted from this is the following. Find the position of an arbitrary maximum in this sequence. Then everything to the left of is is non-increasing. Everything to the right of it is non-increasing.
Thus, for a query, it's enough to consider only two options: the one closest to the maximum from the left and from the right.
Now we only have to learn how to get these options fast enough. For a query $$$(x, y)$$$ we want to solve what's called a diophantine equation $$$ax + by = n$$$. An arbitrary solution can be obtained by using extended Euclid algorithm. Let it be some $$$(a, b)$$$. Then we would want to check the answer for $$$ax$$$ black peppers. The amount of solutions to the equation is either infinite or zero. If it's infinite, all solutions will be of the form $$$ax + k \cdot \mathit{lcm}(x, y)$$$ for any integer $$$k$$$. Remember that not all the solutions will be in a range $$$[0, n]$$$.
Finally, find the two solutions that are the closest to the maximum, check that they are in the range $$$[0, n]$$$ and print the best answer of them.
Overall complexity: $$$O(n \log n + q \log X)$$$.