En el animado mercado agropecuario de La Habana, Daniel vende diferentes productos locales — desde plátanos y mangos hasta café y azúcar.

Cada producto tiene un factor de costo ~a_i~, que representa cuán costoso es venderlo.

Daniel quiere equilibrar sus precios asignando a cada producto un multiplicador de precio ~b_i~, formando un costo total del mercado:

~S = a_1 \times b_1 + a_2 \times b_2 + \ldots + a_N \times b_N~

Él desea que este total ~S~ sea lo más pequeño posible, para mantener sus precios competitivos.

Sin embargo, hay una regla del mercado justo:
ningún multiplicador de precio puede ser usado más de ~K~ veces.

Daniel enfrentará ~Q~ escenarios de inspección, cada uno con un límite máximo de repeticiones ~k_i~.
En cada caso, debe calcular el costo total mínimo ~S~ bajo esa restricción.

Entrada

La primera línea contiene dos enteros ~N~ y ~Q~ (~1 \le N \le 500\,000~, ~1 \le Q \le 750\,000~) — el número de productos y el número de escenarios de inspección.

La segunda línea contiene ~N~ enteros ~a_1, a_2, \ldots, a_N~ (~1 \le a_i \le 1\,000\,000~), los factores de costo de cada producto.

La tercera línea contiene ~Q~ enteros ~k_1, k_2, \ldots, k_Q~ (~1 \le k_i \le 1\,000\,000\,000~), los límites de repetición para cada escenario.

Salida

Imprime una sola línea con ~Q~ enteros — el i-ésimo número es el costo total mínimo del mercado para el i-ésimo escenario.

Subtareas

Subtarea	Condición adicional	Puntos	Dependencia
1	~N \le 5000~	40	Ninguna
2	~N \le 100\,000~	30	Debe pasar la subtarea 1
3	Sin restricciones adicionales	30	Debe pasar la subtarea 2

Ejemplo

Entrada

8 9
40 100 77 15 44 22 47 38
7 5 3 8 4 2 1 6 9

Salida

398 458 579 383 498 741 1273 420 383

Explicación

Para el primer escenario ~K = 7~:
Una posible configuración óptima es ~b = [1, 1, 1, 2, 1, 1, 1, 1]~.
Entonces el costo total del mercado es:
~S = 1 \times 40 + 1 \times 100 + 1 \times 77 + 2 \times 15 + 1 \times 44 + 1 \times 22 + 1 \times 47 + 1 \times 38 = 398~.