고정 길이 K 부분 배열의 최대 합

제한

• $1 \le K \le N \le 10^6$
• $-10^4 \le A_i \le 10^4$
• 답이 64비트 정수 범위 안

입출력 예시

입력 1

6 3
2 5 7 1 3 8

출력 1

14

설명: 길이 3 부분 배열들의 합은 차례로 14, 13, 11, 12. 최댓값은 14 (첫 윈도우 $\{2,5,7\}$).

입력 2

8 4
-1 -2 -3 -4 -5 -6 -7 -8

출력 2

-10

설명: 음수만 있는 배열. 가장 큰 합은 $-1+(-2)+(-3)+(-4) = -10$.

입력 3

5 5
1 2 3 4 5

출력 3

15

설명: $K=N$이면 윈도우가 한 개뿐이고, 전체 합이 답이다.

풀이 힌트

$N$이 크다 ($10^6$). 매 윈도우마다 합을 처음부터 다시 더하면 $O(NK)$로 너무 느리다. 슬라이딩 윈도우로 $O(N)$에 풀자.