题目描述

给定一个长度为 $N$ 的数列 $\{a_i\}$，以及一个满足 $1 \leq K \leq N$ 的整数 $K$。在这个数列中，长度为 $K$ 的连续子序列共有 $N-K+1$ 个。请你求出所有这些长度为 $K$ 的连续子序列的元素和的总和。

输入格式

输入通过标准输入按以下格式给出。

$N$ $K$

$a_1$ .. $a_N$

输出格式

输出所有长度为 $K$ 的连续子序列的元素和的总和，共 $N-K+1$ 个。

输入输出样例 #1

输入 #1

5 3
1 2 4 8 16

输出 #1

49

输入输出样例 #2

输入 #2

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

输出 #2

10988865195

说明/提示

限制条件

• $1 \leq K \leq N \leq 10^5$
• $0 \leq a_i \leq 10^8$
• $a_i$ 为整数。

部分得分

• 对于 50 分的测试点，$N \leq 10^3$。

样例解释 1

$(1+2+4)+(2+4+8)+(4+8+16)=49$，所以答案是 $49$。

样例解释 2

请注意防止溢出。

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载