Trabajo en equipo#10401
Para su festividad favorita, el Granjero John quiere enviar regalos a sus amigos. Como no es muy bueno envolviendo regalos, quiere contar con la ayuda de sus vacas. Como cabría esperar, las vacas tampoco son mucho mejores envolviendo regalos — una lección que el Granjero John está a punto de aprender de la manera difícil.
Las vacas del Granjero John están paradas en una fila, convenientemente numeradas de a en orden. La vaca tiene un nivel de habilidad para envolver regalos de s_i. Estos niveles de habilidad pueden variar considerablemente, por lo que FJ decide dividir a sus vacas en equipos. Un equipo puede consistir en cualquier grupo de como máximo vacas consecutivas, y ninguna vaca puede pertenecer a más de un equipo. Como las vacas aprenden unas de otras, el nivel de habilidad de cada vaca en un equipo puede elevarse al nivel de habilidad de la vaca más hábil de ese equipo.
Ayuda a FJ a determinar la máxima suma posible de niveles de habilidad que puede lograr formando los equipos de manera óptima.
La primera línea contiene dos enteros y k~(1 \le n \le 10^4, 1 \le k \le 10^3). Cada una de las siguientes líneas contiene el nivel de habilidad de una vaca, en el orden en que las vacas están paradas. Cada nivel de habilidad es un entero positivo que no excede 10^5.
Imprime un entero — la máxima suma posible de niveles de habilidad que FJ puede lograr al dividir a las vacas en equipos de vacas consecutivas.
En este ejemplo, la solución óptima es agrupar a las primeras vacas y a las últimas vacas, dejando a la vaca del medio en un equipo ella sola (recuerda que se permiten equipos con menos de vacas). Como resultado, los niveles de habilidad de las vacas se convierten en , , , , , , , que suman .
Ejemplo 1