eolymp
bolt
Try our new interface for solving problems
Problems

The staircase

The staircase

Time limit 1 second
Memory limit 122 MiB

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.

Input 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. Output Print the greatest possible sum of numbers written on the steps, which passed the man.

Examples

Input example #1
3
1 -1 1
2
Output example #1
2