Approximate Median Modification

Farmer John has a binary tree with N nodes (numbered from 1 to N) where N is an odd integer (1 ≤ N < 2×10^5). For every node i > 1, its parent is the node numbered \(\lfloor i/2 \rfloor\). Each node i has an initial integer value \(a_i\) and a cost \(c_i\) (\(0 \le a_i, c_i \le 10^9\)) to change the value to any other integer.

FJ uses a special algorithm to compute an approximate median on this tree. The algorithm works as follows. Starting from the last node \(N\) and moving backwards to node 1:

• If node i has two children (i.e. if both \(2i\) and \(2i+1\) exist) then consider the triple \(\{a_i, a_{2i}, a_{2i+1}\}\). If the value at node i is not the median (i.e. the middle element when sorted) of these three values, then FJ swaps the value of node i with the value equal to the median among its children.

At the end of the algorithm the value at the root (node 1) is output as the approximate median.

The Federal Bovine Intermediary (FBI) has presented FJ with Q independent queries. In each query a target value m (\(0 \le m \le 10^9\)) is given. Before running the algorithm, FJ is allowed to change the initial values of some nodes – changing the value of node i costs \(c_i\) (each node may be changed arbitrarily many times but only the first change incurs the cost). For each query, FJ wants to achieve that the algorithm outputs exactly m while minimizing the total modification cost. Determine the minimum total cost required for each query.

Note: The time limit for this problem is 4 seconds (typically twice the normal limit).

inputFormat

The first line contains two integers N and Q.

The second line contains N integers: \(a_1, a_2, \dots, a_N\).

The third line contains N integers: \(c_1, c_2, \dots, c_N\).

The next Q lines each contain an integer m, representing a query.

outputFormat

For each query, output a single line containing the minimum total cost required so that after modifying some node values and executing the approximate median algorithm the output equals m.

sample

3 2
3 1 2
5 1 1
2
1

0
1