76. Recompensas de hotel
Autor: Fidel I. Schaposnik
Limite de tiempo : 1 seg. Total runs : 1 Aceptados : 1
Planea pasar sus vacaciones recorriendo Europa, quedándose cada noche en una ciudad diferente durante N noches consecutivas. Ya ha elegido el hotel en el que desea alojarse para cada ciudad, por lo que sabe el precio P i de la habitación en la que se alojará durante la i -ésima noche de sus vacaciones, para i = 1,. . . , N .
Reservará su alojamiento a través de un sitio web que tiene un programa de recompensas muy conveniente, que funciona de la siguiente manera. Después de pasar una noche en un hotel que reservó a través de este sitio web, se le otorgará un punto, y en cualquier momento puede intercambiar K de estos puntos en su cuenta por una noche gratis en cualquier hotel (que sin embargo no le dará otro punto) .
Por ejemplo, considere el caso con N = 6 y K = 2 donde los precios de las habitaciones son P 1 = 10, P 2 = 3, P 3 = 12, P 4 = 15, P 5 = 12 y P 6 = 18 Después de pagar las primeras cuatro noches, tendría cuatro puntos en su cuenta, que podría cambiar para quedarse gratis las dos noches restantes, pagando un total de P 1 + P 2 + P 3 + P 4= 40 para su alojamiento. Sin embargo, si después de las primeras tres noches usa dos de los tres puntos que ganó para quedarse la cuarta noche gratis, entonces puede pagar la quinta noche y usar los dos puntos finales para obtener la sexta gratis. En este caso, el costo total de su alojamiento es P 1 + P 2 + P 3 + P 5 = 37, por lo que esta opción es realmente más conveniente.
Desea hacer un programa para averiguar cuál es el costo mínimo posible para el alojamiento de sus vacaciones. Puede suponer con seguridad que todos los hoteles en los que desea alojarse siempre tendrán una habitación disponible y que no se puede alterar el orden de las ciudades que visitará.
Entrada
La primera línea de entrada contiene dos enteros N y K , que representan la cantidad total de noches que durarán sus vacaciones y la cantidad de puntos que necesita para obtener una noche gratis (1? ≤ N , K ≤? 10 5 ). La segunda línea contiene N números enteros P 1 , P 2 ,. . . , P N , que representa el precio de las habitaciones en las que se alojará durante sus vacaciones (1 ≤? P i ≤? 10 4 para i = 1, 2,..., N ).
Salida
Imprima una línea con un número entero que represente el costo mínimo de su alojamiento para todas sus vacaciones.
Ejemplo Entrada
6 2
10 3 12 15 12 18
6 1
10 3 12 15 12 18
5 5
1 2 3 4 5
Ejemplo Salida
37
25
15