你面前的桌子上有 n 堆大小为 a1, a2, ..., an 的石头。
在一次移动过程中,您可以取出一堆并将其添加到另一堆中。当您将堆 i 添加到堆 j 时,堆 j 的大小会增加堆 i 的当前大小,并且堆 i 停止存在。添加操作的成本等于添加的堆的大小。
你的任务是确定将所有石头收集到一堆的最低成本。
为了增加一些挑战,石堆建立了阴谋,并决定每堆让你添加的次数不超过k次(之后只能添加到另一堆)。
此外,这些堆决定让你完全困惑,并告诉你 k 可能等于的 q 个变体(不一定不同)。
你的任务是找到每个 q 个变体的最小成本。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 石堆的数量。第二行包含 n 个空格分隔的整数:a1, a2, ..., an (1 ≤ ai ≤ 109) — 石堆的初始大小。
第三行包含整数 q (1 ≤ q ≤ 105) — 查询数量。最后一行包含 q 个空格分隔的整数 k1, k2, ..., kq (1 ≤ ki ≤ 105) — 不同查询的数字 k 的值。请注意数字 ki 可以重复。
输出
打印 q 个以空格分隔的整数 — 按顺序查询的答案,其中查询在输入中给出。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
5 2 3 4 1 1 2 2 3
输出 #1
9 8
注意
在第一个示例中,获得最佳答案的一种方法是这样的:我们依次将第 4 堆和第 5 堆添加到第 2 堆;然后我们将第一堆添加到第三堆;我们将第二堆添加到第三堆。前两次操作各花费 1;第三个花费2,第四个花费5(前两次操作后第二堆的大小不是3,它已经是5)。
在第二个示例中,您可以将第二堆添加到第三堆(操作成本为 3);然后是第1个到第3个(成本为2);然后是第5个到第4个(成本为1);最后是第4个到第3个(成本为2)。