Problem Description

Given a sequence of length $N$ $\{a_i\}$ and an integer $K$ between $1$ and $N$, the sequence contains $N-K+1$ contiguous subsequences of length $K$. Find the sum of the sums of the values contained in each of these subsequences.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ a_1 $ .. $ a_N $

Output Format

Output the sum of the sums of the values contained in the $N-K+1$ subsequences.

Sample Input and Output

Sample Input #1

5 3
1 2 4 8 16

Sample Output #1

49

Sample Input #2

20 10
100000000 100000000 98667799 100000000 100000000 100000000 100000000 99986657 100000000 100000000 100000000 100000000 100000000 98995577 100000000 100000000 99999876 100000000 100000000 99999999

Sample Output #2

10988865195

Notes/Hints

Constraints

• $1 \leq K \leq N \leq 10^5$
• $0 \leq a_i \leq 10^8$
• $ a_i $ is an integer.

Partial Points

• For 50 points, $N \leq 10^3$.

Sample Explanation 1

Since $ (1+2+4)+(2+4+8)+(4+8+16)=49 $, the answer is $ 49 $.

Sample Explanation 2

Be careful of overflow.

见题面 Input 部分

见题面 Output 部分