CF1728E Red-Black Pepper

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$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$）——第 $i$ 道菜加红辣椒或黑辣椒后的美味度。 接下来一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）——商店数量。 接下来的 $m$ 行，每行包含两个整数 $x_j$ 和 $y_j$（$1 \le x_j, y_j \le n$）——第 $j$ 家商店红辣椒包和黑辣椒包分别能供应的份数。

输出 $m$ 个整数。对于每家商店，输出 Monocarp 只在该店购买辣椒包并为菜肴加辣椒后所有菜肴的最大总美味度。如果无法购买到恰好 $n$ 份辣椒包，请输出 $-1$。

考虑第一个样例。 在第一家商店，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$。 在第四家商店，只能买偶数份辣椒包。由于 $n$ 是奇数，不可能恰好买到 $n$ 份。因此答案为 $-1$。 由 ChatGPT 4.1 翻译