#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=303000;
int n,k,a[N];
pair<ll,int> dp[N][2];
pair<ll,int> solve(ll cst) {
dp[0][0]=mp(0,0);
dp[0][1]=mp(-1e17,0);
rep(i,1,n+1) {
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=max(mp(dp[i-1][1].fi+a[i],dp[i-1][1].se),mp(dp[i-1][0].fi+a[i]-cst,dp[i-1][0].se-1));
}
pair<ll,int> ans=max(dp[n][0],dp[n][1]);
return {ans.fi,-ans.se};
}
int main() {
scanf("%d%d",&n,&k);
rep(i,1,n+1) scanf("%d",a+i);
ll l=0,r=1e15,lmb=0;
while (l<=r) {
ll mid=l+r>>1;
if (solve(mid).se<=k) {
lmb=mid;
r=mid-1;
} else {
l=mid+1;
}
}
pair<ll,int> ans=solve(lmb);
printf("%lld\n",ans.fi+ans.se*lmb);
}
