문제
경수네 학교에서는 반 대항 줄다리기가 열려서 반대표를 뽑아야 한다. 그런데 학교에서는 너무 잘하는 학생들만 뽑으면 결과가 너무 뻔하다는 생각으로 반드시 번호순으로 이웃한 학생끼리만 대표로 선발해야 한다는 규정을 새로 마련했다.
예를 들어 각반 대표선수를 3명을 뽑는다고 할 때 2, 3, 4번 또는 9, 10, 11번 이렇게 차례대로 이웃한 번호끼리 3명을 선발할 수는 있지만 2, 3, 5번과 같이 중간에 번호를 건너 뛰고 선수를 선발해서는 안 된다.
경수네 반에서는 선발되는 학생들의 능력치의 합이 최대가 되도록 선수를 선발하려고 한다.
경수네 반 각 학생들의 능력치를 알고 있을 때 선수로 선발하는 학생들의 능력치의 합을 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에 경수네 반의 학생수 N과 반대표로 선발해야 하는 학생수 M이 입력된다. (1 ≤ M ≤ N ≤ 100,000)
두 번째 줄에는 N명에 대한 능력치가 1번부터 N번까지 번호순으로 입력된다. (능력치는 100 이하의 자연수이다.)
출력
N명을 선발했을 때 최대가 되는 능력치의 합을 출력한다.
예제
10 3
5 9 25 33 11 23 31 29 99 10
159
7번부터 9번까지 대표로 선발하는 경우 31 + 29 + 99 = 159로 최대가 된다.
로그인해야 코드를 작성할 수 있어요.