Problem
Die Heuschrecke springt in gleicher Entfernung voneinander über die Pfosten, die sich auf derselben Linie befinden. Die Spalten haben Sequenznummern von 1 bis N . Am Anfang sitzt die Heuschrecke auf einer Spalte mit der Nummer 1. Er kann in einer Entfernung von 1 zu K Säulen vorwärts springen, wobei er vom aktuellen zählt.
Auf jeder Spalte kann eine Heuschrecke mehrere Goldmünzen gewinnen oder verlieren (für jede Spalte ist diese Zahl bekannt). Bestimmen Sie, wie Sie die Heuschrecke springen müssen, um die größte Anzahl von Goldmünzen zu sammeln. Beachten Sie, dass die Heuschrecke nicht rückwärts springen kann.
Eingabe:
- in der ersten Zeile werden zwei natürliche Zahlen eingegeben: N und K (\(2 <= N ,\ K <= 10000\)), getrennt durch ein Leerzeichen;
- in der zweiten Zeile werden durch ein Leerzeichen N-2 ganze Zahlen geschrieben – die Anzahl der Münzen, die die Heuschrecke auf jeder Spalte erhält, von der 2. bis zur N-1. Wenn diese Zahl negativ ist, verliert die Heuschrecke Münzen.
Es ist garantiert, dass alle Zahlen modulo 10.000 nicht überschreiten.
Ausgabe:
- in der ersten Zeile sollte das Programm die größte Anzahl von Münzen ausgeben, die eine Heuschrecke sammeln kann;
- in der zweiten Zeile wird die Anzahl der Heuschreckensprünge angezeigt;
- in der dritten Zeile – die Nummern aller von der Heuschrecke besuchten Säulen (durch ein Leerzeichen in aufsteigender Reihenfolge).
Wenn es mehrere richtige Antworten gibt, geben Sie eine von ihnen aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|