아이템 2

좌우로 무한히 긴 수직선 위에 $N$개의 아이템이 떨어져 있다. $i$번째 아이템은 위치 $i$에 있으며, 가치는 $A_i$이다.

주원이에게는 길이가 $K$인 집게가 있다. 주원이가 정수 좌표 $x$($-10^9 \le x \le 10^9$)를 지정하면, 집게는 $x$부터 $x+K-1$까지의 범위에 있는 아이템을 모두 줍는다. 주운 아이템은 그 자리에서 사라지며, 다시 내려놓을 수 없다. 주원이는 집게를 원하는 만큼 사용해 주운 아이템 가치의 합을 최대로 만들고자 한다.

주원이가 주운 아이템 가치의 합으로 가능한 값 중 최댓값을 구하여라. 집게를 한 번도 쓰지 않을 수도 있으며, 이때 주운 아이템의 총 가치는 0이다.

첫째 줄에 아이템의 개수 $N$과 집게의 길이 $K$가 주어진다.

둘째 줄에 아이템의 가치 $A_1, A_2, \cdots, A_N$이 차례대로 공백으로 구분되어 주어진다.

주운 아이템 가치의 합으로 가능한 값 중 최댓값을 출력한다.

• $1 \le K \le N \le 500\,000$
• $-500\,000 \le A_i \le 500\,000$ $(1 \le i \le N)$
• 입력으로 주어지는 수는 모두 정수이다.

정답이 32비트 정수 범위를 벗어날 수 있으므로, C/C++에서는 long long 타입을, Java에서는 long 타입을 사용하는 것을 권장한다.