← 返回题目列表

Codeforces · 1728/E

E. 红黑胡椒

中文机器翻译题面 查看原题

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。

输入

第一行包含一个整数 $$$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$$$ 商店中红胡椒包和黑胡椒包足够的份数。

输出

打印 $$$m$$$ 整数。对于每个商店,打印Monocarp仅在该商店购买胡椒包并将胡椒添加到菜肴中后菜肴的最大总味道。如果不可能购买到每道菜都加一次胡椒粉且没有胡椒粉的包装,请打印-1。

示例

输入 #1

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

输出 #1

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

输出 #2

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

注意

考虑第一个例子。

在第一家商店,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$$$。