Planificando el aguinaldo
Aunque muchos de sus amigos de los pueblos cercanos se han pasado a la moda de pedir caramelos en Halloween, el pequeño Alberto Capán Deretas prefiere mantener viva la tradición, mucho más española, de pedir el aguinaldo puerta por puerta en Navidad. Ataviados con panderetas, zambombas y botellas de anís, el año pasado su pandilla consiguió un montón de monedas ¡y algunos billetes! cantando villancicos yendo por todas las casas de su calle.
Este año han decidido organizarse. Tienen apuntado cuánto dinero consiguieron en cada una de las puertas a las que llamaron la última vez y confían en repetir la hazaña. El problema es que se les ha echado el tiempo encima y no pueden ir todos juntos puerta por puerta. Van a separarse en grupos y saben que cada grupo puede pedir el aguinaldo en exactamente k viviendas consecutivas de la calle antes de tener que volver todos a casa para la cena.
Están viendo en cuántos grupos dividirse y en qué secuencia de casas consecutivas pedir cada uno el aguinaldo. La inocencia de la infancia les ha hecho decidir una forma de repartirse la calle poco eficiente. El primer grupo se irá a la secuencia consecutiva de k viviendas en las que el año pasado sacaron más beneficio. El segundo grupo elegirá igual entre las restantes, sabiendo que no pueden pedir el aguinaldo en una casa donde el primer grupo ya lo haya hecho y que las k casas tienen que estar juntas o no les dará tiempo a pasar por todas. Si, al elegir, hay dos secuencias de casas diferentes con el mismo beneficio esperado, el grupo elegirá la que está más cerca del inicio de la calle.
Después de repartirse así el trabajo, se han quedado algunos grupos de casas sueltas a las que nadie irá a pedir el aguinaldo porque no forman grupos de k consecutivas. La pandilla de Alberto no se da cuenta de que seguramente podrían haberse organizado mejor para conseguir más dinero. ¿Cuánto están perdiendo en total?
Entrada
La entrada está compuesta por varios casos de prueba, cada uno formado por dos líneas.
La primera línea contiene dos números, 1 ≤ n ≤ 500.000 y 1 ≤ k ≤ 200.000, indicando respectivamente el número de viviendas en la calle de Alberto, y la cantidad de casas consecutivas a las que un grupo puede pedir el aguinaldo antes de que se haga tarde. Se garantiza que k ≤ n.
La segunda línea contiene n números entre 1 y 100.000 indicando la estimación de la recaudación que conseguirán en cada vivienda. Dos números aparecen seguidos en la entrada si se corresponden con dos viviendas adyacentes.
La entrada termina con 0 0.
Salida
Por cada caso de prueba el programa escribirá cuánta recaudación está desaprovechando la pandilla de Alberto por repartirse la calle de la forma en la que lo hacen.
Entrada de ejemplo
4 2 1 5 4 2 4 2 5 4 2 1 4 2 1 2 2 2 0 0
Salida de ejemplo
3 0 3