Red-Black Pepper

Description:

Input:

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:

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.

Sample Input:

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

Sample Output:

62
112
107
-1

Sample 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

Sample Output:

26
-1
36
30
-1
26
34
26
-1
36

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