Nile

You want to transport $N$ artifacts through the Nile. The artifacts are numbered from $0$ to $N - 1$. The weight of artifact $i$ ($0 \le i < N$) is $W[i]$.

You use specialized boats to transport the artifacts. Each boat can carry at most two artifacts.

• If you put a single artifact in a boat, its weight can be arbitrary.
• If you put two artifacts in the same boat, the boat must be balanced. Specifically, artifacts $p$ and $q$ ($0 \le p < q < N$) can share a boat only when their weights differ by at most $D$, that is, $|W[p] - W[q]| \le D$.

The cost of transporting artifact $i$ ($0 \le i < N$) depends on how many artifacts share its boat:

• $A[i]$, if the artifact rides in its own boat.
• $B[i]$, if the artifact shares a boat with another artifact.

In the second case, you pay for both artifacts in the boat. If artifacts $p$ and $q$ ($0 \le p < q < N$) share a boat, you pay $B[p] + B[q]$.

A boat with a single artifact always costs more than sharing, so $B[i] < A[i]$ for every $i$ ($0 \le i < N$).

The river conditions are hard to predict, so the value of $D$ changes often. Answer $Q$ questions numbered from $0$ to $Q - 1$. The questions are given as an array $E$ of length $Q$. The answer to question $j$ ($0 \le j < Q$) is the minimum total cost of transporting all $N$ artifacts when $D$ equals $E[j]$.

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le W[i] \le 10^9$ for every $i$ ($0 \le i < N$)
• $1 \le B[i] < A[i] \le 10^9$ for every $i$ ($0 \le i < N$)
• $1 \le E[j] \le 10^9$ for every $j$ ($0 \le j < Q$)