The grasshopper jumps on columns located on the same line at equal distances from each other. The columns have serial numbers from 1 to N . At the beginning, the Grasshopper sits on a post with the number 1. It can jump forward from 1 to K bars, counting from the current one.
On each column, the Grasshopper can gain or lose several gold coins (this number is known for each column). Determine how the Grasshopper needs to jump in order to collect the most gold coins. Keep in mind that the Grasshopper cannot jump backwards.
Input:
- the first line contains two natural numbers: N and K (\(2 <= N ,\ K < = 10000\)), space-separated;
- in the second line, space-separated N-2 integers – the number of coins the Grasshopper gets on each column, from 2nd to N-1th. If this number is negative, the Grasshopper loses coins.
It is guaranteed that all numbers in modulo do not exceed 10000.
Output:
- in the first line, the program should display the maximum number of coins that the Grasshopper can collect;
- the second line displays the number of Grasshopper's jumps;
- on the third line – numbers of all columns visited by the Grasshopper (separated by a space in ascending order).
If there are several correct answers, print any of them.
Examples
| # |
Input |
Output |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|