#include <bits/stdc++.h>
using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db;

#define int ll

const int N = 3e5 + 10;

mt19937 mt( (ull)( &N ) );
int Rand ( int l, int r ) { return uniform_int_distribution<int>(l,r)(mt); }

int n, k, m, A[N], S[N]; pair<int,int> F[N];

int Sum ( int l, int r  ) { return S[r] - S[l-1]; }

int Val ( int l, int r )
{
    int mid = l + ( r - l >> 1 );
    if( ( r - l + 1 ) & 1 ) return Sum( mid + 1, r ) - Sum( l, mid - 1 );
    else                    return Sum( mid + 1, r ) - Sum( l, mid     );
}

pair<int,int> Cost ( int p, int i ) {
    return make_pair(  F[p].first + Val( p + 1, i ) - m, F[p].second + 1 );
}

pair<int,int> Check ( int mid )
{
    m = mid;

    static struct Ver { int p, l, r; } V[N];

    int head = 1, tail =  0;
    V[++tail] = { 0, 1, n };
    for( int i = 1; i <= n; ++i )
    {
        while( head < tail && V[head].r < i ) ++head; V[head].l = i;
        F[i] = Cost( V[head].p,  i );
        while( head < tail && Cost( i, V[tail].l ) < Cost( V[tail].p, V[tail].l ) ) --tail;

        int l = V[tail].l, r = V[tail].r + 1;
        while( r - l > 1 )
        {
            int mid = l + r >> 1;
            if( Cost( i, mid ) < Cost( V[tail].p, mid ) ) r = mid; else l = mid;
        }
        if( r <= n ) V[tail].r = r - 1, V[++tail] = { i, r, n };
    }
    return F[n];
}

void Solve ()
{
    cin >> n >> k;
    for( int i = 1; i <= n; ++i ) cin >> A[i], S[i] = S[i-1] + A[i];

    int l = - (ll)INT_MAX * 2000, r = 0, res = 0;
    while( r - l > 1 )
    {
        int mid = l + ( r - l >> 1 );
        if( Check( mid ).second <= k ) l = mid, res = mid; else r = mid;
    }
    pair<int,int> ans = Check( res );
    cout << ans.first + k * res << "\n";
}

signed main() 
{
    ios::sync_with_stdio( false ), cin.tie(0), cout.tie(0); Solve();
    return 0;
}