题目描述

给定一个长度为 $N$ 的正整数序列 $v_1, v_2, \dots, v_N$，以及一个整数 $A$。

你可以对数组执行任意多次相邻交换。一次交换可以交换相邻的两个元素 $v_i$ 和 $v_{i+1}$，其代价为：

$$v_i + v_{i+1}$$

交换后，数组变为：

$$v_1, \dots, v_{i+1}, v_i, \dots, v_N$$

对于某个给定的整数 $R$，定义最终代价为：

$$(\text{所有交换操作的总代价}) + (v_1 + v_2 + \cdots + v_R)\times A$$

其中 $v_1,\dots,v_R$ 指的是经过若干次交换后的新数组的前 $R$ 个元素。

现在有 $Q$ 次询问。第 $i$ 次询问给出一个 $R_i$。对于每次询问，你需要在该询问独立的前提下，求出最小可能总代价。

注意：所有询问彼此独立。

输入格式

第一行包含三个整数 $N,Q,A$，分别表示数组长度、询问个数以及系数 $A$。

第二行包含 $N$ 个正整数 $v_1,v_2,\dots,v_N$，表示初始数组。

第三行包含 $Q$ 个正整数 $R_1,R_2,\dots,R_Q$，表示所有询问。

输出格式

对于每个询问，输出一行一个整数，表示对应询问的最小总代价。

数据范围

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

子任务

子任务	额外限制	分值
1	$N\le 8,\ Q=1$	5
2	$N\le 5000,\ Q=1$	10
3	$N\le 10^6,\ Q=1$	25
4	$N\le 1.5\times 10^4$	10
5	$N\le 5\times 10^4$	50

只有通过某个子任务的全部测试点，才能获得该子任务的分数。

样例 1

输入

4 1 5
4 1 2 3
2

输出

25

样例 1 说明

最优策略是不进行任何交换。

此时代价为：

$$(4+1)\times 5 = 25$$

样例 2

输入

4 1 6
4 1 2 3
2

输出

29

样例 2 说明

可以先交换 $4$ 和 $1$，再交换 $4$ 和 $2$：

4 1 2 3
1 4 2 3
1 2 4 3

两次交换的代价分别为：

• 第一次：$4+1=5$
• 第二次：$4+2=6$

最终数组前 $2$ 个数之和为 $1+2=3$，所以总代价为：

$$5+6+(1+2)\times 6 = 29$$