import java.io.*;
import java.util.*;
public class feast {
static int n;
static int k;
static long[][][] dp;
static long[] A;
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
dp = new long[n+1][2][2];
dp[0][1][0] = -1000000000000000000L;
A = new long[n+1];
st = new StringTokenizer(br.readLine());
for(int i=1; i<=n; i++)
A[i] = Integer.parseInt(st.nextToken());
long l = 0;
long r = 1000000000000000L;
while(l<r) {
long m =(l+r)/2;
if(solve(m))r = m;
else l = m+1;
}
solve(l);
out.write(better(dp[n][0],dp[n][1])[0]+l*k+"\n");
out.flush();
out.close();
}
static boolean solve(long v) {
for(int i=1; i<=n; i++) {
dp[i][0] = better(dp[i-1][0], dp[i-1][1]);
dp[i][1] = better(new long[]{dp[i-1][0][0]+A[i]-v, dp[i-1][0][1]+1},new long[]{dp[i-1][1][0]+A[i],dp[i-1][1][1]});
}
return better(dp[n][0], dp[n][1])[1]<=k;
}
static long[] better(long[] a, long[]b) {
if(a[0]==b[0])return (a[1]<b[1] ? a:b);
return (a[0] > b[0] ? a: b);
}
}
