Bessie y su hermanita Elsie están recogiendo cerezas en la parcela de cerezas del Granjero Juan. La parcela del Granjero Juan tiene exactamente ~N~ árboles de cerezas; el árbol ~i~ contiene exactamente ~B_i~ cerezas. Bessie tiene exactamente ~K~ canastas, ~K~ par). Cada canasta puede tener tantas cerezas de un solo árbol como Bessie quiera, pero no puede contener cerezas de dos árboles diferentes pues sus sabores se pelearan entre ellos. Las canastas pueden permanecer vacías.

Beesie quiere maximizar el número de cerezas que ella recoja. Sin embargo, el Granjero Juan quiere que Bessie comparta con su hermanita, y por lo tanto Bessie tendrá que darle a Elsie las ~K/2~ canastas con el mayor número de cerezas. Esto quiere decir que Elise podría terminar con más cerezas que Bessie, lo cual es muy injusto, pero desafortunadamente, las relacioens entre hermanas no son siempre justas.

Ayude a Bessie a encontrar el número máximo de cerezas que ella puede recoger.

Entrada

• La primera línea de la entrada contiene dos enteros separados por espacio ~N~ y ~K~.
• La segunda línea contiene ~N~ enteros separados por espacios ~B_1,B_2,...,B_N~.

Salida

Una línea simple con la respuesta.

Restricciones

• ~1 \leq N \leq 1000~
• ~1 \leq B_i \leq 1000~
• ~1 \leq K \leq 1000~

Ejemplo de Entrada

5 4
3 6 8 4 2

Ejemplo de Salida

8

Si Bessie llena

• una canasta con 6 cerezas del árbol 2
• dos canastas, cada una con 4 cerezas del árbol 3
• una canasta con 4 cerezas del árbol 4

entonces ella recibe dos canastas cada una con 4 cerezas, dando 8 cerezas en total.

USACO 2020 January Contest, Silver Problem 1. Berry Picking.