Viajando con el abuelo
En unos días comienzan por fin mis vacaciones. Cargaré las maletas en el coche y emprenderé un largo viaje para alejarme de la ciudad e irme al pueblo. Bueno, antes de coger la carretera pasaré a buscar a mi abuelo, que se viene conmigo para pasar unos días con los pocos amigos de juventud que le quedan vivos.
Aunque me encanta viajar con él escuchando todas las historias que me cuenta tiene una pequeña pega. El aguante de su vejiga ya no es el que era y tengo que parar más veces de las que pararía si fuera yo solo. A él le preocupa también bastante el asunto y quiere saber de antemano cuánto tiempo tendrá que esperar como mucho entre parada y parada, para ver si se viene conmigo o se coge el autobús.
Yo tengo claro el número máximo de descansos que estoy dispuesto a hacer y tengo una estimación de lo que se tarda en ir desde cada área de descanso de la ruta a la siguiente. Ahora tengo que planificar las paradas para minimizar lo que tiene que aguantarse el abuelo.
Entrada
La entrada está compuesta de distintos casos de prueba cada uno ocupando dos líneas.
La primera línea de cada caso contiene dos números: la cantidad n de tramos en los que está dividido el viaje (1 ≤ n ≤ 100.000) y el número máximo de paradas p que estoy dispuesto a hacer antes de llegar al destino (0 ≤ p ≤ 10.000). La segunda línea contiene n números con el tiempo necesario para recorrer cada tramo (un número entre 1 y 10.000).
El primer tramo es el que va desde la casa del abuelo a la primera área de descanso, y el último el que va desde la última área de descanso hasta el lugar de destino.
Salida
Por cada caso de prueba se escribirá una única línea con el tiempo máximo que estará el abuelo aguantando, teniendo en cuenta que como mucho haremos p paradas. No quiero hacer sufrir al abuelo (ni que termine montándome un espectáculo en el coche) por lo que ese tiempo debe ser lo menor posible.
Ten en cuenta que lo último que hace el abuelo antes de salir de casa y lo primero que hace al llegar al destino es ir al baño.
Entrada de ejemplo
2 1 6 4 3 0 3 6 5 3 1 3 6 5
Salida de ejemplo
6 14 9