Removiendo el Prado
Después de ganar la competencia anual del pueblo para el mejor prado hace un año, el Granjero Juan se ha vuelto perezoso; no ha removido el prado desde entonces y por lo tanto su prado está descuidado. Sin embargo, pronto la competencia se va a volver a efectuar, y GJ quiere poner en forma su prado de tal manera que él pueda reclamar el titulo.
Desafortunadamente, GJ se ha dado cuenta que su prado está tan descuidado, que él necesitará la ayuda de algunas de sus vacas, las cuales están alineadas en una fila y numeradas convenientemente . Algunas vacas son más eficientes que otras moviendo el prado; la vaca i tiene eficiencia .
GJ se ha dado cuenta que frecuentemente las vacas vecinas en la fila frecuentemente se conocen bien entre ellas; también ha descubierto que si él elige más de K vacas (1 <= K <= N) vacas consecutivas (adyacentes) para que lo ayuden, ellas no le prestarán atención al prado y en vez de esto comenzaran una fiesta. Por lo tanto, GJ necesita que usted lo ayude: determine la mayor eficiencia total que GJ puede obtener sin elegir más de vacas consecutivas.
Entrada
Línea 1: Dos enteros separados por espacio: y
Líneas 2..N+1: La línea i+1 contiene un solo entero:
Ejemplo de Entrada
5 2
1
2
3
4
5
Detalles de la Entrada:
GJ tiene vacas cuyas eficiencias son y , en ese orden. El quiere elegir algunas de las vacas de tal manera que su eficiencia total sea maximizada, pero él no puede elegir más de vacas consecutivas.
Salida
- Línea 1: Un solo entero que es la mejor eficiencia que GJ puede obtener.
Salida
12
Detalles de la Salida
GJ elige todas las vacas menos la tercera. La eficiencia total de las vacas es por lo tanto
Comments