Crafts Transport Problem

You want to transport N handcrafted items along the Nile. The items are numbered from 0 to N-1. The weight of the i-th item is \(W[i]\).

To transport these items, you have a special boat that can carry at most two items.

• If an item is shipped alone, its shipping cost is \(A[i]\) (and the boat can handle any weight in this case).
• If you decide to ship two items together, the boat must remain balanced. In particular, if you want to load items \(p\) and \(q\) together (with \(0 \le p < q < N\)) then you must have \(|W[p] - W[q]| \le D\). In that case, the cost for item \(i\) (where \(i = p\) or \(q\)) is \(B[i]\); note that you pay for both items in the boat, so the pair costs \(B[p] + B[q]\).

It is guaranteed that for every item \(i\), \(B[i] < A[i]\); that is, shipping an item alone is always more expensive than pairing it (if pairing is possible).

You are given \(Q\) queries. In the \(j\)-th query the parameter \(D\) becomes \(E[j]\). For each query, compute the minimum total cost to transport all \(N\) items.

Note: The total cost is determined by deciding, for each item, whether it is shipped alone (costing \(A[i]\)) or paired with another item (where each item in the pair costs \(B[i]\)). Since shipping an item alone is always more expensive than pairing it, the problem becomes one of finding a pairing (subject to the weight difference condition) that maximizes your cost saving. In particular, if an item \(i\) is paired then you save \(A[i] - B[i]\). Thus, if you let \(\Delta_i = A[i]-B[i]\) and have a valid pairing covering a set of items, then the total cost is equal to \(\sum_{i=0}^{N-1} A[i] - \) (sum of \(\Delta_i\) for items that are paired).

inputFormat

The first line contains an integer \(N\) representing the number of items.

The second line contains \(N\) space-separated integers representing \(W[0], W[1], \ldots, W[N-1]\).

The third line contains \(N\) space-separated integers representing \(A[0], A[1], \ldots, A[N-1]\).

The fourth line contains \(N\) space-separated integers representing \(B[0], B[1], \ldots, B[N-1]\).

The fifth line contains an integer \(Q\) representing the number of queries.

The sixth line contains \(Q\) space-separated integers representing \(E[0], E[1], \ldots, E[Q-1]\).

outputFormat

Output \(Q\) lines. The \(j\)-th line should contain the minimum total cost of transporting all items when \(D = E[j]\).

sample

3
10 12 15
5 6 7
3 4 5
2
2 5

14
14

</p>