문제
농부 존은 작년 잔디밭 가꾸기 대회에서 우승한 이후로 잔디밭을 관리하지 않은 바람에 잔디밭이 난장판이 되었다. 농부 존은 올해에도 잔디밭 가꾸기 대회를 한다는 소식을 듣고 부랴부랴 대회를 준비하기 시작했다.
농부 존은 소들을 불러서 잔디 관리 일을 시키려고 한다. N마리의 소들이 일렬로 서 있으며, 각 소의 능률은 Ei이다. 농부 존은 N마리 중에서 일부를 선택해서 일을 시킬 것이다.
여러 마리의 소들이 연속해 있으면 모여서 놀기 때문에, 농부 존은 연속해서 K마리보다 많은 소들에게 일을 시키면 안 된다. 농부 존은 소들이 놀지 않게 적절히 일할 소를 정할 것이다. 농부 존을 도와 일하는 소들의 능률의 합이 최대가 되도록 소들에게 일을 시키는 프로그램을 작성하여라.
입력
첫 번째 줄에는 소의 마리수 N과 최대로 연속해서 선택할 수 있는 소의 수 K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
두 번째 줄부터 N개의 줄에는 각 소의 능률 Ei (0 ≤ Ei ≤ 1,000,000,000)가 주어진다.
출력
일하는 소를 적절히 선택했을 때 능률 합의 최댓값을 출력한다.
예제
5 2
1
2
3
4
5
12
힌트
태그
출처
USACO US Open 2011 Contest - Gold 1번
로그인해야 코드를 작성할 수 있어요.