나일

나일강을 통해 $N$개의 유물을 운반하려고 한다. 유물에는 $0$부터 $N - 1$까지 번호가 붙어 있다. 유물 $i$ ($0 \le i < N$)의 무게는 $W[i]$이다.

유물은 전용 배로 운반한다. 각 배에는 최대 두 개의 유물을 실을 수 있다.

• 배에 유물을 하나만 실는 경우, 그 유물의 무게에는 제한이 없다.
• 배에 유물을 두 개 실는 경우, 배의 균형이 맞아야 한다. 구체적으로, 유물 $p$와 $q$ ($0 \le p < q < N$)는 무게 차이가 $D$ 이하일 때, 즉 $|W[p] - W[q]| \le D$일 때만 같은 배에 실을 수 있다.

유물 $i$ ($0 \le i < N$)의 운반 비용은 같은 배에 실린 유물의 수에 따라 달라진다.

• 유물이 배를 혼자 쓰면 $A[i]$를 낸다.
• 유물이 다른 유물과 배를 함께 쓰면 $B[i]$를 낸다.

후자의 경우 배에 실린 두 유물의 비용을 모두 낸다. 유물 $p$와 $q$ ($0 \le p < q < N$)를 같은 배에 실으면 $B[p] + B[q]$를 낸다.

배를 혼자 쓰는 비용은 항상 함께 쓰는 비용보다 비싸다. 따라서 모든 $i$ ($0 \le i < N$)에 대해 $B[i] < A[i]$이다.

강의 상태는 예측하기 어려워서 $D$ 값이 자주 바뀐다. $Q$개의 질문에 답하라. 질문은 길이가 $Q$인 배열 $E$로 주어진다. 질문 $j$ ($0 \le j < Q$)의 답은 $D$가 $E[j]$일 때 전체 $N$개 유물을 운반하는 최소 총비용이다.

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• 모든 $i$ ($0 \le i < N$)에 대해 $1 \le W[i] \le 10^9$
• 모든 $i$ ($0 \le i < N$)에 대해 $1 \le B[i] < A[i] \le 10^9$
• 모든 $j$ ($0 \le j < Q$)에 대해 $1 \le E[j] \le 10^9$