Problems
The staircase
The staircase
At each of the \textbf{n} + \textbf{2} steps of the staircase an integer is written, on the first and last step there is a number \textbf{0}. The man stands on the first step. He must climb the last step. In one step, he can rise any number of steps not greater than \textbf{k}.
Find the sum of all the numbers written on the steps, which came a man. Find the largest possible value of this amount.
\textbf{Input } The first line contains the number \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{1000}). On the second line \textbf{n} integers written on the steps are given (except on the first and the last step, which contain zero). They do not exceed \textbf{1000} by absolute value and are separated by spaces. The maximum length of the man's step \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{n}) is given in the third line. \textbf{Output} Print the greatest possible sum of numbers written on the steps, which passed the man.
Input example #1
3 1 -1 1 2
Output example #1
2