시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

예제 입력

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

예제 출력

195

힌트