Maximum Fatigue Accumulation

A salesman, Aming, has been sent to Screws Street to promote his company's products. Screws Street is a dead‐end street where the entrance and exit are the same, with a wall on one side and houses on the other. There are \(N\) households on Screws Street; the \(i\)th household is at a distance \(S_i\) meters from the entrance, and promoting to the \(i\)th household increases Aming's fatigue by \(A_i\) points. Note that several households can be at the same distance.

Aming enters the street and visits exactly \(X\) households (in the order they appear along the street), then returns by the same route. Every meter walked increases his fatigue by 1 point. Since he only goes as far as necessary, his walking fatigue is exactly \(2 \times d\) points, where \(d\) is the distance to the farthest visited household. That is, if his chosen set of households (of size \(X\)) has promotion fatigue sum \(P\) and the farthest distance is \(d\), his total accumulated fatigue is \(P+2d\).

Your task is: given the positions \(S_i\) and promotion fatigue values \(A_i\) for the \(N\) households and \(Q\) queries (each query is a positive integer \(X\), with \(X \le N\)), compute the maximum total fatigue Aming can accumulate by choosing exactly \(X\) households under the condition that he does not walk extra distance. In other words, for each query, choose a subset of \(X\) households (the farthest of which is at distance \(d\)) such that the value \[ \text{Total Fatigue} = \Bigl(\sum_{i \in \text{chosen}} A_i\Bigr) + 2\,d \] is maximized.

Input/Output note: You are given \(N\) and \(Q\) in the first line. The next line contains \(N\) integers denoting \(S_1, S_2, \dots, S_N\). The following line contains \(N\) integers denoting \(A_1, A_2, \dots, A_N\). Then \(Q\) lines follow, each containing one integer \(X\). For each query, output the maximum fatigue value on a separate line.

inputFormat

The input begins with a line containing two integers \(N\) and \(Q\) (the number of households and the number of queries). The next line contains \(N\) integers \(S_1,S_2,\dots,S_N\) (the distances of the households from the entrance). The following line contains \(N\) integers \(A_1,A_2,\dots,A_N\) (the fatigue incurred by promoting to the corresponding household). Then \(Q\) lines follow, each containing one integer \(X\) (the number of households Aming must visit).

outputFormat

For each query, output on a separate line a single integer representing the maximum total fatigue Aming can accumulate by visiting exactly \(X\) households.

sample

5 3
1 2 2 4 5
3 1 2 10 1
1
3
5

18
25
27