## Lamp

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

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