#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pub push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll Max=1e5+5;
pll dp[Max][2];
ll a[Max],n,k;
pll process(ll la)
{
ll i,j;
dp[1][0]={0,0};
dp[1][1]={a[1]-la,1};
for(i=2;i<=n;++i)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=max(mp(dp[i-1][0].fi+a[i]-la,dp[i-1][0].se+1),mp(dp[i-1][1].fi+a[i],dp[i-1][1].se));
}
pll res=max(dp[n][0],dp[n][1]);
return res;
}
ll solve()
{
ll i,j,l,r;
l=0;
r=1e18;
//cout<<l<<" "<<r<<"\n";
while(l<=r)
{
ll mid=(l+r)>>1;
pll res=process(mid);
//cout<<"mid="<<mid<<" dp="<<res.fi<<" cnt="<<res.se<<"\n";
if(res.se==k)
{
/*for(i=1;i<=n;++i)
{
cout<<i<<".\n";
auto x=dp[i][0];
cout<<"dp="<<x.fi<<" cnt="<<x.se<<"\n";
x=dp[i][1];
cout<<"dp="<<x.fi<<" cnt="<<x.se<<"\n";
}*/
return res.fi+res.se*mid;
}
if(res.se>k)
l=mid+1;
else r=mid-1;
}
return 0;
}
int main()
{
fast
ll i,j;
cin>>n>>k;
for(i=1;i<=n;++i)
cin>>a[i];
ll ans=solve();
cout<<ans;
return 0;
}
