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 int n, c;
public static long v;
public static long[][] dp;
public static int[][] cnt;
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) {
dp = new long[n][2];
cnt = new int[n][2];
dp[0][1] = a[0] - l;
cnt[0][1] = 1;
for (int i = 1; i < n; i++) {
max(dp[i - 1][0], cnt[i - 1][0], dp[i - 1][1], cnt[i - 1][1]);
dp[i][0] = v;
cnt[i][0] = c;
max(dp[i - 1][0] - l, cnt[i - 1][0] + 1, dp[i - 1][1], cnt[i - 1][1]);
dp[i][1] = v + a[i];
cnt[i][1] = c;
}
max(dp[n - 1][0], cnt[n - 1][0], dp[n - 1][1], cnt[n - 1][1]);
}
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();
}
}
