Монокарп собирается устроить вечеринку для своих друзей. Он приготовил \(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.
Выходные данные
Выведите \(m\) целых чисел. Для каждого магазина выведите максимальную суммарную вкусность блюд, после того как Монокарп купит упаковки перца только в этом магазине и добавит перец в блюда. Если невозможно купить упаковки так, чтобы в каждое блюдо добавить перец один раз и чтобы перца не осталось, то выведите -1.
Примечание
Рассмотрим первый пример.
В первом магазина Монокарп может купить только \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 10
100 50
2 2
4
2 3
1 1
3 2
2 2
|
62
112
107
-1
|
|
2
|
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
|