#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define maxN 10002
#define maxK 1002
using namespace std;
int n, i, j, k, v[maxN], sum, dp[maxK][maxN], sol, s[maxN];
deque < pair < int, int > > d;
void read()
{
    freopen("ferma.in", "r", stdin);
    scanf("%d %d", &n, &k);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]),
             s[i] = v[i] + s[i - 1];
}
void solve()
{
    int Max;
    for(i = 1; i <= k; ++ i)
    {
        Max = dp[i - 1][i - 1] - s[i - 1];
        for(j = i; j <= n; ++ j)
        {
            dp[i][j] = max(dp[i][j - 1], Max + s[j]);
            Max = max(Max, dp[i - 1][j] - s[j]);
        }
    }
    sol = dp[k][n];
    dp[1][1] = v[1];
    for (i = 2; i <= n; ++ i)
        dp[1][i] = max(dp[1][i - 1], s[i]);

    for(i = 2; i <= k; ++ i)
    {
        Max = dp[i - 1][i - 1] - s[i - 1];
        for(j = i; j <= n; ++ j)
        {
            dp[i][j] = max(dp[i][j - 1], Max + s[j]);
            if (i == k && sol < dp[i][j] + s[n] - s[j])
               sol = dp[i][j] + s[n] - s[j];
            Max = max(Max, dp[i - 1][j] - s[j]);
        }
    }
}
void print()
{
    freopen("ferma.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    print();
    return 0;
}