← 返回题目列表

Codeforces · 1132/B

B. 折扣

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

您来到当地一家商店想要购买一些巧克力棒。商店里有 $$$n$$$ 条,其中 $$$i$$$ 需要花费 $$$a_i$$$ 硬币(并且您想购买全部)。

您有 $$$m$$$ 不同的优惠券可让您购买巧克力棒。第 $$$i$$$ 优惠券允许您购买 $$$q_i$$$ 巧克力棒,而您只需支付 $$$q_i - 1$$$ 最贵的巧克力棒(因此,这些 $$$q_i$$$ 巧克力棒中最便宜的巧克力棒是免费的)。

您只能使用一张优惠券;如果您使用优惠券$$$i$$$,则必须选择$$$q_i$$$金条并使用优惠券购买它们,并购买所有剩余的$$$n - q_i$$$金条,没有任何折扣。

要决定选择哪张优惠券,您想知道如果您最佳地使用其中一张优惠券,您必须支付的最低总金额是多少。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 商店中巧克力棒的数量。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 块巧克力的成本。

第三行包含一个整数 $$$m$$$ ($$$1 \le m \le n - 1$$$) — 您拥有的优惠券数量。

第四行包含 $$$m$$$ 整数 $$$q_1$$$, $$$q_2$$$, ..., $$$q_m$$$ ($$$2 \le q_i \le n$$$),其中 $$$q_i$$$ 是您必须使用第 $$$i$$$ 优惠券购买的巧克力棒数量,这样其中最便宜的巧克力棒将是免费的。 $$$q_i$$$ 的所有值都是成对不同的。

输出

打印 $$$m$$$ 整数,其中 $$$i$$$-th 应该是您使用第 $$$i$$$ 优惠券购买 $$$q_i$$$ 金条时需要支付的最低金额,其余所有金条一一按全价购买。

示例

输入 #1

7
7 1 3 1 4 10 8
2
3 4

输出 #1

27
30

注意

考虑第一个例子。

如果我们使用第一张优惠券,我们可以选择索引为$$$1$$$、$$$6$$$和$$$7$$$的巧克力棒,并为它们支付$$$18$$$硬币,为所有其他巧克力棒支付$$$9$$$硬币。

如果我们使用第二张优惠券,我们可以选择索引为$$$1$$$、$$$5$$$、$$$6$$$和$$$7$$$的巧克力棒,并为它们支付$$$25$$$硬币,为所有其他巧克力棒支付$$$5$$$硬币。