import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class feast {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static long v,dp1p,dp0p,dp1,dp0;
public static int n,c,cnt1,cnt0,cnt0p,cnt1p;
public static int[] a;
public static void main(String[] args) {
// TODO code application logic here
n = nextInt();
int k = nextInt();
a = new int[n];
long hi = 0, lo = 0, mid, intv;
for (int i = 0; i < n; i++) {
int in = nextInt();
a[i] = in;
hi += Math.abs(in);
}
hi += 1;//maybe double
while (lo < hi - 1) {
mid = (lo + hi) >> 1;
solveL(mid);
intv = c;
if (intv >= k) {
lo = mid;
} else {
hi = mid;
}
}
solveL(lo);
System.out.println((v + k * lo));
}
public static void solveL(long l) {
dp0p=0;
dp1p=a[0]-l;
cnt1p = 1;
cnt0p=0;
for (int i = 1; i < n; i++) {
max(dp0p, cnt0p, dp1p, cnt1p);
dp0 = v;
cnt0 = c;
max(dp0p- l, cnt0p + 1, dp1p, cnt1p);
dp1 = v + a[i];
cnt1 = c;
dp0p=dp0;
dp1p=dp1;
cnt0p=cnt0;
cnt1p=cnt1;
}
max(dp0, cnt0, dp1, cnt1);
}
public static void max(long p10, int p11, long p20, int p21) {
if ((p10 == p20) ? ((p11 >= p21)) : ((p10 > p20))) {
v = p10;
c = p11;
} else {
v = p20;
c = p21;
}
}
public static int nextInt() {
return Integer.parseInt(next());
}
public static String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
}
