reorder

You are given N numbers – $v_1, v_2, ...,v_N$, and an integer A. You can do an unlimited number of swaps in the array by swapping $v_i$ and $v_{i+1}$ for a cost of $v_i+v_{i+1}$. The new array after the swap would then be $v_1,…,v_{i+1},v_i,…,v_N$. For a certain number R, your task it to find the minimum sum of the costs of your swaps and $(v_1+v_2+...+v_R) \cdot A$. Given Q queries and an $R_i$ for each of them, find the minimum cost you can achieve for each query. All queries are independent.

Input

There are 3 integers on the first line: N – the size of the array, Q – the number of queries and A – the coefficient $(v_1+v_2+...+ v_R)$ is multiplied by. The second line of the input contains N positive integers $v_1,...,v_N$ - the starting array. The last line holds the positive integers $R_1,...,R_Q$.

Output

On each of the Q lines output the minimum cost for the corresponding query.

Constraints

• $1 ≤ Q, R_i ≤ N$
• $1 ≤ v_i, A ≤ 10^6$

Subtask 1 (5 points)

• N ≤ 8
• Q = 1

Subtask 2 (10 points)

• N ≤ 5 000
• Q = 1

Subtask 3 (25 points)

• $N ≤ 10^6$
• Q = 1

Subtask 4 (10 points)

• $N ≤ 1.5 \cdot 10^4$

Subtask 5 (50 points)

• $N ≤ 5 \cdot 10^4$

Examples

stdin

4 1 5
4 1 2 3
2

stdout

25

stdin

4 1 6
4 1 2 3
2

stdout

29

Explanation

Example 1: It is optimal to not swap any elements. The cost is then (4 + 1) × 5 = 25.

Example 2: We can first swap 4 with 1 and then 4 with 2:
4 1 2 3
1 4 2 3
1 2 4 3

The costs of the swaps are 4+1=5 and 4+2=6. Therefore, the total cost is 5+6+(1+2)×6=29.