Problem
O gafanhoto salta em colunas localizadas na mesma linha a distâncias iguais umas das outras. As colunas têm números de série de 1 a N . No início, o Gafanhoto senta-se em um poste com o número 1. Ele pode avançar de 1 para K barras, contando a partir da atual.
Em cada coluna, o Gafanhoto pode ganhar ou perder várias moedas de ouro (esse número é conhecido para cada coluna). Determine como o Gafanhoto precisa pular para coletar o maior número de moedas de ouro. Tenha em mente que o Gafanhoto não pode pular para trás.
Entrada:
- a primeira linha contém dois números naturais: N e K (\(2 <= N ,\ K < = 10000\)), separados por espaços;
- na segunda linha, inteiros N-2 separados por espaços – o número de moedas que o Gafanhoto recebe em cada coluna, de 2 a N-1th. Se este número for negativo, o Gafanhoto perde moedas.
É garantido que todos os números no módulo não excedam 10000.
Saída:
- na primeira linha, o programa deve exibir o número máximo de moedas que o Gafanhoto pode coletar;
- a segunda linha exibe o número de saltos do Gafanhoto;
- na terceira linha – números de todas as colunas visitadas pelo Grasshopper (separadas por um espaço em ordem crescente).
Se houver várias respostas corretas, imprima qualquer uma delas.
Exemplos
| # |
Entrada |
Saída |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|