Descripción

Dado ~N~ números – ~v_1 , v_2 , ... , v_N~, y un entero ~A~. Se pueden realizar un ilimitado número de swaps en el arreglo intercambiando ~v_i~ y ~v_{i + 1}~ por un costo de ~v_i + v_{i + 1}~. Entonces el nuevo arreglo luego del swap será ~v_1 , ... , v_{i+1} , v_i , ... , v_N~.

Tarea

Para cierto número ~R~, su tarea sera encontrar la suma mínima de dos valores (los costos de los swaps y (~v_1~ + ~v_2~ + ... + ~v_R~) × ~A~). Dados ~Q~ consultas y un ~R_i~ para cada uno de estos, encuentre el costo mínimo que se puede lograr para cada consulta. Todas las consultas son independientes.

Entrada

Se darán ~3~ enteros en la primera linea: ~N~ – tamaño del arreglo, ~Q~ – número de consultas y ~A~ – el coefiiente que multilica a ~(v_1 + v_2 + ... + v_R)~.

La segunda linea contine ~N~ enteros positios ~v_1~ , ⋯ , v~_N~ el arreglo inicial..

La última linea da los enteros positios ~R_1..., R_Q~

Salida

En cada una de las ~Q~ lineas imprima el costo mínimo para cada consulta.

Restricciones

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

Subtareas

№ Restricciones Adicionales Puntos

1 | ~N \le 8~ | ~Q = 1~ | puntos 5

2 | ~N \le 5000~ | ~Q = 1~ | puntos 10

3 | ~N \le 10^6~ | ~Q = 1~ | puntos 25

4 | ~N \le 10^4~ | \(-¿\) | puntos 10

5 | \(N \le 5 × 10^4\) | \(-¿\) | puntos 50

Se darán puntos por cada subtarea solo si se pasan todos sus casos

Ejemplo de Entrada #1

4 1 5
4 1 2 3
2

Ejemplo de Salida #1

25

Ejemplo de Entrada #2

4 1 6
4 1 2 3
2

Ejemplo de Salida #2

29

Explicación de los ejemplos

Ejemplo №1: Es optimo no swapear ningun elemento. Entonces el costo será \((4 + 1) × 5 = 25\).

Ejemplo №2: Podemos swapear ~4~ con ~1~ primero y luego ~4~ con ~2~:

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

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

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

El costo de los swaps es ~4 + 1 = 5~ y ~4 + 2 = 6~. Entonces, el costo total es \(5 + 6 + (1 + 2) × 6 = 29\).