You are given numbers , and an integer . You can do an unlimited number of swaps in the array by swapping and for a cost of . The new array after the swap would then be . For a certain number , your task it to find the minimum sum of the costs of your swaps and . Given queries and an for each of them, find the minimum cost you can achieve for each query. All queries are independent.
输入格式
There are 3 integers on the first line: – the size of the array, – the number of queries and – the coefficient is multiplied by. The second line of the input contains positive integers - the starting array. The last line holds the positive integers .
输出格式
On each of the lines output the minimum cost for the corresponding query.
样例
样例输入 1
4 1 5
4 1 2 3
2
样例输出 1
25
样例输入 2
4 1 6
4 1 2 3
2
样例输出 2
29
数据范围与提示
Explanation of the examples
Example 1: It is optimal to not swap any elements. The cost is then .
Example 2: We can first swap with and then with :
4 1 2 3
1 4 2 3
1 2 4 3
The costs of the swaps are and . Therefore, the total cost is
