Red-Black Pepper

题意翻译

有 $n$ 盘菜，每盘菜要加入红辣椒或黑辣椒，其中第 $i$ 盘菜加入红辣椒会增加 $a_i$ 点美味值，黑辣椒增加 $b_i$ 点。（每盘菜都会且只会加入一份红辣椒或一份黑辣椒，且不能两种都加） 现在有 $m$ 个商店，每个商店 $j$ 有无数包两种辣椒，一包红辣椒有 $x_j$ 份红辣椒，一包黑辣椒有 $y_j$ 份黑辣椒（每份辣椒只可以加入一盘菜），求对于每个商店，若**只从这个商店买辣椒**得到的最大美味值是多少（买到的辣椒**份数**必须正好等于 $n$，不能多也不能少，若无法实现则输出 $-1$）。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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

**红辣椒与黑胡椒**

**题意翻译：**
有 $ n $ 盘菜，每盘菜可以选择加入红辣椒或黑胡椒。第 $ i $ 盘菜加入红辣椒会增加 $ a_i $ 点美味值，加入黑胡椒则增加 $ b_i $ 点。每盘菜只能加入一种辣椒，不能两种都加。

现有 $ m $ 个商店，每个商店 $ j $ 有两种辣椒包，一包红辣椒有 $ x_j $ 份，一包黑胡椒有 $ y_j $ 份。要求从每个商店购买辣椒，使得加入菜中的辣椒份数正好为 $ n $，求从每个商店购买辣椒所能得到的最大美味值。如果无法实现，则输出 $-1$。

**题目描述：**
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 \times 10^5 $）——菜的数量。

接下来的 $ n $ 行中的第 $ i $ 行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \le a_i, b_i \le 10^9 $）——第 $ i $ 道菜加入红辣椒和黑胡椒后的美味值。

接下来的一行包含一个整数 $ m $（$ 1 \le m \le 3 \times 10^5 $）——商店的数量。

接下来的 $ m $ 行中的第 $ j $ 行包含两个整数 $ x_j $ 和 $ y_j $（$ 1 \le x_j, y_j \le n $）——第 $ j $ 家商店红辣椒和黑胡椒包足够供应的份额。

**输出格式：**
输出 $ m $ 个整数。对于每家商店，输出Monocarp只在这家商店购买辣椒包并在菜中加入辣椒后，菜品的最大总美味值。如果无法购买辣椒包使得每道菜都添加一次辣椒且没有辣椒剩余，则输出 -1。**红辣椒与黑胡椒** **题意翻译：** 有 $ n $ 盘菜，每盘菜可以选择加入红辣椒或黑胡椒。第 $ i $ 盘菜加入红辣椒会增加 $ a_i $ 点美味值，加入黑胡椒则增加 $ b_i $ 点。每盘菜只能加入一种辣椒，不能两种都加。 现有 $ m $ 个商店，每个商店 $ j $ 有两种辣椒包，一包红辣椒有 $ x_j $ 份，一包黑胡椒有 $ y_j $ 份。要求从每个商店购买辣椒，使得加入菜中的辣椒份数正好为 $ n $，求从每个商店购买辣椒所能得到的最大美味值。如果无法实现，则输出 $-1$。 **题目描述：** 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 \times 10^5 $）——菜的数量。 接下来的 $ n $ 行中的第 $ i $ 行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \le a_i, b_i \le 10^9 $）——第 $ i $ 道菜加入红辣椒和黑胡椒后的美味值。 接下来的一行包含一个整数 $ m $（$ 1 \le m \le 3 \times 10^5 $）——商店的数量。 接下来的 $ m $ 行中的第 $ j $ 行包含两个整数 $ x_j $ 和 $ y_j $（$ 1 \le x_j, y_j \le n $）——第 $ j $ 家商店红辣椒和黑胡椒包足够供应的份额。 **输出格式：** 输出 $ m $ 个整数。对于每家商店，输出Monocarp只在这家商店购买辣椒包并在菜中加入辣椒后，菜品的最大总美味值。如果无法购买辣椒包使得每道菜都添加一次辣椒且没有辣椒剩余，则输出 -1。