The staircase

The staircase

At each of the n + 2 steps of the staircase an integer is written, on the first and last step there is a number 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 k.

Find the sum of all the numbers written on the steps, which came a man. Find the largest possible value of this amount.


The first line contains the number n (0n1000). On the second line n integers written on the steps are given (except on the first and the last step, which contain zero). They do not exceed 1000 by absolute value and are separated by spaces. The maximum length of the man's step k (1kn) is given in the third line.


Print the greatest possible sum of numbers written on the steps, which passed the man.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
1 -1 1
Output example #1