Nile

문제

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

To transport the artifacts, you use specialized boats. Each boat can carry at most two artifacts.

• If you decide to put a single artifact in a boat, the artifact weight can be arbitrary.
• If you want to put two artifacts in the same boat, you have to make sure the boat is balanced evenly. Specifically, you can send artifacts $pp$ and $qq$ (0 &le; p < q < N) in the same boat only if the absolute difference between their weights is at most $DD$, that is |W[p] - W[q]| &le; D.

To transport an artifact, you have to pay a cost that depends on the number of artifacts carried in the same boat. The cost of transporting artifact $ii$ (0 &le; i < N) is:

• $A[i]A[i]$, if you put the artifact in its own boat, or
• $B[i]B[i]$, if you put it in a boat together with some other artifact.

Note that in the latter case, you have to pay for both artifacts in the boat. Specifically, if you decide to send artifacts $pp$ and $qq$ (0 &le; p < q < N) in the same boat, you need to pay $B[p]+B[q]B[p]\; +\; B[q]$.

Sending an artifact in a boat by itself is always more expensive than sending it with some other artifact sharing the boat with it, so for all $ii$ such that 0 &le; i < N.

Unfortunately, the river is very unpredictable and the value of $DD$ changes often. Your task is to answer $QQ$ questions numbered from $00$ to $Q-1Q\; -\; 1$. The questions are described by an array $EE$ of length $QQ$. The answer to question $jj$ (0 &le; j < Q) is the minimum total cost of transporting all $NN$ artifacts, when the value of $DD$ is equal to $E[j]E[j]$.