E. Красно-черный перец
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп собирается устроить вечеринку для своих друзей. Он приготовил $$$n$$$ блюд и уже собирается их подать. Сначала он должен добавить в них молотый перец — иначе блюда будут совсем безвкусными.

У $$$i$$$-го блюда есть два значения $$$a_i$$$ и $$$b_i$$$ — его вкусность, если добавить красный или черный перец, соответственно. Монокарп не будет добавлять оба перца ни в какое блюдо, не будет добавлять перец несколько раз и не оставит ни одно блюдо без перца.

До того как добавить перец, Монокарп должен купить этот самый перец в магазине. У него есть неподалеку $$$m$$$ магазинов. В $$$j$$$-м из них продаются упаковки красного перца, которых хватает на $$$x_j$$$ порций, и упаковки черного перца, которых хватает на $$$y_j$$$ порций.

Монокарп идет ровно в один магазин, покупает несколько (возможно, ноль) упаковок каждого перца таким образом, чтобы добавить в каждое блюдо перец ровно один раз и чтобы перца не осталось. Более формально, если он покупает $$$x$$$ упаковок красного перца и $$$y$$$ упаковок черного перца, то $$$x$$$ и $$$y$$$ должны быть неотрицательными, а $$$x \cdot x_j + y \cdot y_j$$$ должно быть равно $$$n$$$.

Для каждого магазина определите максимальную суммарную вкусность блюд, после того как Монокарп купит упаковки перца только в этом магазине и добавит перец в блюда. Если невозможно купить упаковки описанным образом, то выведите -1.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество блюд.

В $$$i$$$-й из следующих $$$n$$$ строк записаны два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — вкусность $$$i$$$-го блюда, если добавить красный или черный перец, соответственно.

В следующей строке записано одно целое число $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — количество магазинов.

В $$$j$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$x_j$$$ и $$$y_j$$$ ($$$1 \le x_j, y_j \le n$$$) — количество порций, на которое хватает упаковки красного и черного перца в $$$j$$$-м магазине, соответственно.

Выходные данные

Выведите $$$m$$$ целых чисел. Для каждого магазина выведите максимальную суммарную вкусность блюд, после того как Монокарп купит упаковки перца только в этом магазине и добавит перец в блюда. Если невозможно купить упаковки так, чтобы в каждое блюдо добавить перец один раз и чтобы перца не осталось, то выведите -1.

Примеры
Входные данные
3
5 10
100 50
2 2
4
2 3
1 1
3 2
2 2
Выходные данные
62
112
107
-1
Входные данные
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
Выходные данные
26
-1
36
30
-1
26
34
26
-1
36
Примечание

Рассмотрим первый пример.

В первом магазина Монокарп может купить только $$$0$$$ упаковок красного перца и $$$1$$$ упаковку черного перца. Если добавить черный перец во все блюда, то получится $$$10 + 50 + 2 = 62$$$.

Во втором магазине Монокарп может купить любое количество упаковок красного и черного перца: $$$0$$$ и $$$3$$$, $$$1$$$ и $$$2$$$, $$$2$$$ и $$$1$$$ или $$$3$$$ и $$$0$$$. Лучшим выбором оказывается либо $$$1$$$ и $$$2$$$, либо $$$2$$$ и $$$1$$$. Монокарп может добавить черный перец в первое блюдо, красный перец во второе блюдо и любой перец в третье блюдо, сумма равна $$$10 + 100 + 2 = 112$$$.

В третьем магазине Монокарп может купить только $$$1$$$ упаковку красного перца и $$$0$$$ упаковок черного перца. Если добавить красный перец во все блюда, то получится $$$5 + 100 + 2 = 107$$$.

В четвертом магазине Монокарп может купить только четное суммарное количество упаковок. Так как $$$n$$$ нечетное, невозможно купить ровно $$$n$$$ упаковок. Поэтому ответ равен $$$-1$$$.