천문대의 관측 계획

문제

한 천문대에서 N일 연속으로 이어지는 밤의 관측 계획을 세우려 한다. 밤은 1일부터 N일까지 번호가 붙어 있다. i번째 밤에 관측하면 관측 가치 b_i 를 얻는다. 장비 점검과 인건비 때문에 b_i 는 음수일 수도 있으며, 이는 관측할수록 손해라는 뜻이다. 각 밤마다 관측할지 말지를 정한다. 관측한 밤들의 관측 가치의 합을 총 가치라고 하자. 단, 장비가 식어 버리는 것을 막기 위해 다음 규칙을 지켜야 한다. 1일부터 N일 사이에서 연속한 K일을 골랐을 때, 그 K일 동안 한 번도 관측하지 않는 경우가 있어서는 안 된다. 즉 밤 1일부터 N일까지 중 어떤 연속한 K일도 전부 관측하지 않는 밤으로만 이루어지면 안 된다. N 이 K 보다 작으면 연속한 K일이 존재하지 않으므로 한 번도 관측하지 않아도 된다. 관측하지 않은 밤이 하나도 없어도 되고, 규칙을 만족하는 한 몇 번을 관측해도 된다. 규칙을 지키면서 얻을 수 있는 총 가치의 최댓값을 구하는 프로그램을 작성하시오. 아무것도 관측하지 않았을 때의 총 가치는 0 이다.

입력

첫 줄에 정수 N 과 K 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 200,000)
둘째 줄에 b_1, b_2, ..., b_N 이 공백으로 구분되어 주어진다. (-1,000,000,000 ≤ b_i ≤ 1,000,000,000, 정수)

출력

총 가치의 최댓값을 한 줄에 출력한다.

7 3
5 -4 -6 8 -10 -10 3

16

2 5
-3 -1

0

4 1
3 -5 4 -1

1

출처: Devin.KR 자체 제작