Estás planeando un viaje para visitar N atracciones turísticas. Las atracciones están numeradas del 1 al N y deben visitarse en este orden. Puedes visitar al día como mucho, K atracciones y deseas planificar el viaje para que tome la menor cantidad de días posible.

Bajo estas limitaciones, desea encontrar un horario que tenga un buen equilibrio entre las atracciones visitadas cada día. Para ser precisos, asignamos una puntuación ai a la atracción i. Dado un horario, cada día recibe una puntuación igual a la puntuación máxima de todas las atracciones visitadas ese día. Finalmente, se suman las puntuaciones de cada día para obtener la puntuación total del programa. ¿Cuál es la máxima puntuación total posible del programa, utilizando el menor número de días posible?

Entrada

La primera línea contiene dos números enteros separados por espacios \(N , K (1≤K≤N≤10^6).\)

La siguiente línea contiene N enteros separados por espacios \(ai (1≤ai≤10^9).\)

Salida

Genera un solo entero, la máxima puntuación total posible.

Ejemplo de Entrada 1

5 3
2 5 7 1 4

Ejemplo de Salida 1

12

Explicacion del Ejemplo

Necesitamos tener al menos dos días para visitar todas las atracciones, ya que no podemos visitar todas las atracciones en un día.

Visitar las dos primeras atracciones el día 1 dará una puntuación de 5, y visitar las tres últimas atracciones el día 2 dará una puntuación de 7, para una puntuación total de 12.

Visitar tres atracciones el día 1 y dos atracciones el día 2, que es la única posibilidad de visitar en el menor número de días posible, arrojaría una puntuación total de