시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB340944820.961%

문제

kcm1700은 심심한 나머지 ntopia에게 다음과 같은 과제를 제시했다. 원형으로 N개의 수가 놓여 있는데, 인접하게 고르는 것이 없게 하면서 K개의 수를 골랐을 때 최대한 K개의 수의 합을 크게 하여라. 인접하게 고른다는 것은 선택한 것 중에 연속되게 놓여있는 두 개의 수를 고른 것이 있다는 뜻이다.

당신은 kcm1700을 무너뜨리고 ntopia를 돕기 위해 원형으로 놓인 N개의 수를 인접하지 않게 K개를 골랐을 때의 최대 합을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 양의 정수 N(3 ≤ N ≤ 1,000,000)과 정수 K(1 ≤ K ≤ N/2) 주어진다. 둘째 줄에는 원을 이루는 N개의 자연수(231 미만)가 시계방향 순서대로 빈 칸을 사이에 두고 차례대로 주어진다.

출력

첫째 줄에 최대 합을 구하여라. 답은 231 보다 작다.

예제 입력 1

10 4
2 1 3 1 2 1 3 1 3 1

예제 출력 1

11

출처

Contest > koi4u > koi4u 2008년 5월 모의고사 E번