#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int MAXN = 3e5+5;
long long n,k;
long long a[MAXN];
void read()
{
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
}
long long dp[MAXN][2];
long long cnt[MAXN][2];
long long check(long long c, bool add)
{
for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = cnt[i][0] = cnt[i][1] = 0;
dp[0][1] = -c;
cnt[0][1] = 1;
for(int i = 1; i <= n; i++)
{
if(dp[i-1][0] > dp[i-1][1])
{
dp[i][0] = dp[i-1][0];
cnt[i][0] = cnt[i-1][0];
}
else
{
dp[i][0] = dp[i-1][1];
cnt[i][0] = cnt[i-1][1];
//if(dp[i-1][0] == dp[i-1][1]) cnt[i][0] = max(cnt[i-1][1],cnt[i-1][0]);
}
if(dp[i-1][0] - c > dp[i-1][1])
{
dp[i][1] = dp[i-1][0] - c + a[i];
cnt[i][1] = cnt[i-1][0] + 1;
}
else
{
dp[i][1] = dp[i-1][1] + a[i];
cnt[i][1] = cnt[i-1][1];
//if(dp[i-1][0] - c == dp[i-1][1]) cnt[i][1] = max(cnt[i-1][0] + 1, cnt[i-1][1]);
}
}
int b = 1;
if(dp[n][0] > dp[n][1]/* || (dp[n][0] == dp[n][1] && cnt[n][0] > cnt[n][1])*/) b = 0;
if(add) return dp[n][b] + c*k;
return (bool)cnt[n][b] >= k;
}
void solve()
{
long long l = 0, r = 1e15;
long long mid;
while(l <= r)
{
mid = (l+r)/2;
if(check(mid,0)) l = mid+1;///absolutno taka e
else r = mid-1;
}
//cout << r << endl;
cout << check(r,1) << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read();
solve();
return 0;
}
