Middle Earth Technical University has a river that passes through it. There are some park benches near the river. It becomes too dark at night and the university wants to build a lamp that can lighten the benches around it.

The lamp will light the square it's built on and the squares within the range of it. The lamp's range is \(K\). Can you find the maximum number of park benches that can be lightened?

You have one lamp. You can put your lamp on any square you want.

Input

First-line contains the integers \(N\) (number of squares) and \(K\) (the range of the lamp).

The second line contains an array of \(N\) nonnegative integers. \(A_i\) correspond to the number of benches in \(i^{th}\) square.

• \(1 \leq \mathbf{N} \leq 10^{5}\)
• \(0 \leq \mathbf{K} \leq 10^{5}\)
• \(1 \leq \mathbf{A_i} \leq 10^{5}\)

Output

Print the maximum number of benches that can be lightened.

Examples

Input:

6 2
1 2 3 4 5 6

Output:

20

Input:

7 1
4 3 2 1 3 4 5

Output:

12