# Appreciation

/*
 * Problem :: 2228 / 구간 나누기
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 6 2
 *   -1 3 1 2 4 -1
 *   + 음...
 *     구간1  5 1
 *     [] + -1 3 1 2 4 -1
 *     구간1   4 1
 *     [-1] + 1 2 4 -1
 *     또는
 *     구간1     3 1
 *     [-1,3] + 2 4 -1
 *     이렇게 나눌 수 있겠는데?
 *     # DP 로 풀라는 것이군
 *       주어진 배열을 A 라고 하고 dp[i][j] 를 다음과 같이 정의하자
 *       dp[i][j] = i 번째부터 N 번째까지 구간 j 개로 나누었을 때
 *                  구간에 속한 수들의 총합의 최댓값
 *       -> i 번째부터 구간을 정하면
 *          [] <= dp[i+1][j]
 *          [A[i]] <= A[i] + dp[i+2][j-1]
 *          [A[i], A[i+1]] <= A[i] + A[i+1] + dp[i+3][j-1]
 *          [A[i], A[i+1], A[i+2]] <= A[i] + A[i+1] + A[i+2] + dp[i+4][j-1]
 *          ...
 *          [A[i], A[i+1], A[i+2], ..., A[N]]
 *          으로 나눌 수 있겠다
 *          => dp[i][j] = max({dp[i+1][j], A[i]+dp[i+2][j-1], ..., })
 *
 * Point
 * - 불가능한 경우를
 *   INF 를 정의해서 -INF 를 반환하는 것으로 구현하였다
 *
 * - dp 에 -1 의 값도 들어갈 수 있기에
 *   if (dp[n][m] != -1) 로 DP 를 구현하는 것은 위험해보였다
 *   + 배열 A 가 모두 -1 로 이루어졌다면...?
 *     # 그렇기에 (bool) isVisited 배열을 선언해서
 *       이를 이용해 DP 를 구현하였다
 *
 * - for 문으로 풀기에는 좀 까다로워서...
 *   함수로 풀었다
 *   + 근데 경게조건을 정하는데 좀 애먹었다
 *     f(int n, int m) = n 번째부터 N 번째까지 
 *                       구간 m 개로 나누었을 때 구간에 속한 수들의 총합의 최댓값
 *     # n > N 이고 m > 0 이면
 *       더이상 수를 선택할 수 없음에도 구간을 만들어야 하므로 불가능한 경우
 *     # n > N 이고 m == 0 이면
 *       더이상 수를 선택할 수 없고 구간도 다 만들었으므로 가능한 경우
 *     # n <= N 이고 m > 0 이면
 *       수를 선택할 수 있고 구간도 만들 수 있으므로 가능한 경우
 *     # n <= N 이고 m == 0 이면
 *       수를 선택할 수 있지만 구간을 이미 다 만들었으므로 가능한 경우
 *       -> 즉, m == 0 이면 return 0
 *          그 다음 n > N 이면 return -INF
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M;
int A[100+1];
int dp[100+1][50+1];
bool isVisited[100+1][50+1];
#define INF 987654321

// Set up : Functions Declaration
int f(int n, int m);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N >> M;
    for (int i=1; i<=N; i++)
        cin >> A[i];

    // Process
    fill(&dp[0][0], &dp[N][M+1], -INF); /* dp 를 음의 무한대로 초기화 */
    int ans = f(1, M); /* dp[1][M] */

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int n, int m)
/* n 번째부터 N 번째까지 구간 m 개로 나누었을 때 구간에 속한 수들의 총합의 최댓값 */
{
    /* 더이상 수를 선택할 수 없음에도 구간을 만들어야 하므로 불가능한 경우 */
    // if (n > N && m > 0) return -INF;
    /* 더이상 수를 선택할 수 없지만 구간을 이미 다 만들었으므로 가능한 경우 */
    // if (n > N && m == 0) return 0;
    /* 수를 선택할 수 있지만 구간을 이미 다 만들었으므로 가능한 경우 */
    // if (n <= N && m == 0) return 0;

    /* 위 코드와 아래의 코드의 로직은 서로 같음 */
    if (m == 0) return 0;
    if (n > N) return -INF;

    /* 이전에 f(n, m) 이 방문된 적 있다면 이전에 계산된 dp[n][m] 값 반환 */
    if (isVisited[n][m]) return dp[n][m];

    isVisited[n][m] = true; /* 방문처리 */
    dp[n][m] = f(n+1, m); /* 구간을 만들지 않고 다음 번째 수로 넘어감 */
    int sum = 0;
    for (int i=n; i<=N; i++) { /* n~i 번째 수로 이루어진 구간을 만들고
                                * i+2 번째 수로 넘어감 */
        sum += A[i];
        dp[n][m] = max(dp[n][m], sum+f(i+2, m-1));
    }
    return dp[n][m];
}