시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3317545.455%

문제

Byteman wants to go for a vacation and he would like to select the best days for that. He bases his choices on a weather forecast for the next 3n days. He is only interested in the highest temperature anticipated for a given day.

Byteman is additionally constrained by terms set by his boss. During any consecutive n days he can take no more than k days of absence. What is the best way to plan the vacation, so that the sum of temperatures in the selected days is maximized?

입력

The first line of the input contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ 10, k < n). In the second line there are 3n positive integers not exceeding 106 that describe the temperatures anticipated for each of the next 3n days.

출력

Your program should output a single integer: the maximum possible sum of temperatures during vacation days picked with respect to boss' terms.

예제 입력 1

5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35

예제 출력 1

195

출처

Camp > POI Training Camp > ONTAK 2010 3-3번