#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 if(dp[i-1][0]<dp[i-1][1])
{
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]);
}
else
{
dp[i][0]=dp[i-1][1];
cnt[i][0]=max(cnt[i-1][0],cnt[i-1][1]);
}
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]);
}
if(dp[i-1][0]-c==dp[i-1][1])
cnt[i][1]=max(cnt[i-1][1],cnt[i-1][0]);
}
/*cout << "THE C " << c << endl;
for(int i = 1; i <= n; i++)
{
cout << " { " << dp[i][0] << " - " << dp[i][1] << " } ";
}
cout << endl;
cout << "CNTs" << endl;
for(int i = 1; i <= n; i++)
{
cout << " { " << cnt[i][0] << " - " << dp[i][1] << " } ";
}
cout << endl;*/
int b = 1;
if(dp[n][0] > dp[n][1]/* || (dp[n][0] == dp[n][1] && cnt[n][0] > cnt[n][1])*/) b = 0;
//cout << "the final = " << dp[n][b] + c*k << " + the cntnb " << cnt[n][b] << " thek " << k << endl;
if(add) return dp[n][b] + c*k;
return (bool)(cnt[n][b] >= k);
}
void solve()
{
long long l = 0, r = 100;
long long mid;
while(l <= r)
{
mid = (l+r)/2;
bool what = check(mid,0);
if(what) l = mid+1;///absolutno taka e
else r = mid-1;
//cout << "after: " << what << " " << l << " " << r << endl ;
//cout << endl;
}
//cout << r << endl;
if(r==-1)r=0;
cout << check(r,1) << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read();
solve();
return 0;
}
