P11049 [IOI 2024] 尼罗河船运
题目背景
这是一道交互题，你只需要实现代码中要求的函数。
你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。
本题仅支持 C++ 语言提交。但请勿使用 C++14 (GCC 9)
题目描述
你想通过尼罗河来运输 $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$ 件手工艺品的最小总代价。
输入格式
评测程序按如下顺序读取输入数据：
```plain
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]
```
输出格式
评测程序按如下顺序输出：
```plain
R[0]
R[1]
...
R[S-1]
```
这里，$S$ 是 `calculate_costs` 所返回的数组 $R$ 的长度。
说明/提示
## 实现细节
你需要实现以下函数。
```
std::vector calculate_costs(
std::vector W, std::vector A,
std::vector B, std::vector 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}$。
## 子任务
| 子任务 | 分数 | 额外的约束条件 |
| :----: | :--: | ------------------------------------------------------------ |
| 1 | $6$ | $Q \leq 5$；$N \leq 2000$；对每个满足 $0 \leq i < N$ 的 $i$，都有 $W[i] = 1$ |
| 2 | $13$ | $Q \leq 5$；对每个满足 $0 \leq i < N$ 的 $i$，都有 $W[i] = i+1$ |
| 3 | $17$ | $Q \leq 5$；对每个满足 $0 \leq i < N$ 的 $i$，都有 $A[i] = 2$ 且 $B[i] = 1$ |
| 4 | $11$ | $Q \leq 5$；$N \leq 2000$ |
| 5 | $20$ | $Q \leq 5$ |
| 6 | $15$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $A[i] = 2$ 且 $B[i] = 1$ |
| 7 | $18$ | 没有额外的约束条件。 |
## 例子
考虑以下调用。
```
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]$。