Problem
El saltamontes salta sobre columnas ubicadas en la misma línea a la misma distancia entre sí. Las columnas tienen números de serie de 1 a N . Al principio, el saltamontes se sienta en un poste con el número 1. Puede saltar de barras 1 a K, contando desde la barra actual.
En cada columna, el Saltamontes puede ganar o perder varias monedas de oro (este número se conoce para cada columna). Determina cómo debe saltar el saltamontes para recolectar la mayor cantidad de monedas de oro. Tenga en cuenta que el saltamontes no puede saltar hacia atrás.
Entrada:
- la primera línea contiene dos números naturales: N y K (\(2 <= N ,\ K < = 10000\)), separados por espacios;
- en la segunda línea, enteros N-2 separados por espacios – el número de monedas que obtiene el Saltamontes en cada columna, desde la 2ª hasta la N-1ésima. Si este número es negativo, el Saltamontes pierde monedas.
Se garantiza que todos los números en módulo no excedan 10000.
Salida:
- en la primera línea, el programa debe mostrar la cantidad máxima de monedas que el Saltamontes puede recolectar;
- la segunda línea muestra el número de saltos de Grasshopper;
- en la tercera línea – números de todas las columnas visitadas por Grasshopper (separadas por un espacio en orden ascendente).
Si hay varias respuestas correctas, imprima cualquiera de ellas.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|