N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M(1≤M≤N/2 올림)개의 구간으로 나눠서 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.
1. 하나의 구간은 하나 이상의 연속된 수들로 이루어진다.
2. 두 개의 구간이 서로 겹치거나 붙어 있어서는 안 된다.
3. M개의 구간이 모두 있어야 한다. M개 이하가 아니다.
N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수이다.
출력
첫째 줄에 답을 출력한다.