题目描述

你想通过尼罗河来运输 $N$ 件手工艺品。这些手工艺品从 $0$ 到 $N-1$ 编号。第 $i$（$0 \leq i < N$）件手工艺品的重量是 $W[i]$。

为了运输这些手工艺品，你使用了特制的船。每艘船最多可以运两件手工艺品。

• 如果你决定将单件手工艺品放在一艘船上，那么这件手工艺品的重量可以是任意的。
• 如果你想把两件手工艺品一起放在同一艘船上，你必须保证这艘船的平衡。具体来说，如果手工艺品 $p$ 和 $q$（$0 \leq p < q < N$）的重量差的绝对值不超过 $D$，即满足 $|W[p] - W[q]| \leq D$，那么你可以将它们一起放在同一艘船上。

你必须付费来运一件手工艺品，其运费取决于同一艘船上所运载的手工艺品数量。手工艺品 $i$（$0 \leq i < N$）的运费是：

• $A[i]$，如果你把手工艺品 $i$ 单独放在船上，或者
• $B[i]$，如果你把手工艺品 $i$ 和另一件手工艺品一起放在船上。

注意在第二种情况中，你要为船上两件手工艺品都支付运费。具体来说，如果你决定用同一艘船运输手工艺品 $p$ 和 $q$（$0 \leq p < q < N$），你需要支付 $B[p] + B[q]$。

一件手工艺品单独用一艘船运输的费用，总是比与其他手工艺品合用一艘船时的费用要高，所以对任意满足 $0 \leq i < N$ 的 $i$，都有 $B[i] < A[i]$。

麻烦的是，由于尼罗河变化莫测，导致 $D$ 的值经常改变。你的任务是回答 $Q$ 个问题，从 $0$ 到 $Q-1$ 编号。这些问题用一个长度为 $Q$ 的数组 $E$ 来描述。问题 $j$（$0 \leq j < Q$）的答案，是在 $D$ 的值等于 $E[j]$ 时运输所有 $N$ 件手工艺品的最小总代价。

实现细节

你需要实现以下函数。

std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A, 
    std::vector<int> B, std::vector<int> E)

• $W$，$A$，$B$：长度均为 $N$ 的整数数组，分别给出手工艺品的重量和运费。
• $E$：长度为 $Q$ 的整数数组，给出每个问题中的 $D$ 值。
• 该函数应该返回一个包含 $Q$ 个整数的数组 $R$，给出运输手工艺品的最小总代价，其中 $R[j]$ 对应 $D$ 等于 $E[j]$（对每个满足 $0 \leq j < Q$ 的 $j$）时的运费。
• 对于每个测试用例，该函数恰好被调用一次。

约束条件

• $1 \leq N \leq 100\,000$
• $1 \leq Q \leq 100\,000$
• 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq W[i] \leq 10^{9}$
• 对每个满足 $0 \leq i < N$ 的 $i$，都有 $1 \leq B[i] < A[i] \leq 10^{9}$
• 对每个满足 $0 \leq j < Q$ 的 $j$，都有 $1 \leq E[j] \leq 10^{9}$

子任务

例子

考虑以下调用。

calculate_costs([15, 12, 2, 10, 21],
                [5, 4, 5, 6, 3],
                [1, 2, 2, 3, 2],
                [5, 9, 1])

在该例子中，我们有 $N=5$ 件手工艺品和 $Q=3$ 个问题。

在第一个问题中，$D = 5$。你可以把手工艺品 $0$ 和手工艺品 $3$ 放在同一艘船上（因为 $|15 - 10| \leq 5$），而其他手工艺品都各自放在不同的船上。这使得运输所有手工艺品的总代价最小，即 $1+4+5+3+3 = 16$。

在第二个问题中，$D = 9$。你可以把手工艺品 $0$ 和手工艺品 $1$ 放在同一艘船上（因为 $|15 - 12| \leq 9$），而把手工艺品 $2$ 和手工艺品 $3$ 放在同一艘船上（因为 $|2 - 10| \leq 9$）。剩下的手工艺品单独用一艘船运输。这使得运输所有手工艺品的总代价最小，即 $1+2+2+3+3 = 11$。

在最后一个问题中，$D = 1$。你需要把每件手工艺品都单独用一艘船运输。这使得运输所有手工艺品的总代价最小，即 $5+4+5+6+3 = 23$。

因此，该函数应该返回 $[16, 11, 23]$。

评测程序示例

输入格式：

N
W[0] A[0] B[0]
W[1] A[1] B[1]
...
W[N-1] A[N-1] B[N-1]
Q
E[0]
E[1]
...
E[Q-1]

输出格式：

R[0]
R[1]
...
R[S-1]

这里，$S$ 是 calculate_costs 所返回的数组 $R$ 的长度。

时间限制：$\texttt{2s}$

空间限制：$\texttt{2048MB}$