#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main(){
int N, K; cin>>N>>K;
vector<int> A(N);
for(int i = 0; i < N; i++){
cin>>A[i];
}
auto solve_lambda = [&](int lambda) {
vector<vector<int>> dp(N, vector<int>(2));
vector<vector<int>> count(N, vector<int>(2));
dp[0][1] = A[0] - lambda;
count[0][1] = 1;
for(int i = 1; i < N; i++){
auto [a, b] = max(
make_pair(dp[i - 1][0], count[i - 1][0]),
make_pair(dp[i - 1][1], count[i - 1][1])
);
dp[i][0] = a;
count[i][0] = b;
auto [c, d] = max(
make_pair(dp[i - 1][0] + A[i] - lambda, count[i - 1][0] + 1),
make_pair(dp[i - 1][1] + A[i], count[i - 1][1])
);
dp[i][1] = c;
count[i][1] = d;
}
return max(
make_pair(dp[N - 1][0], count[N - 1][0]),
make_pair(dp[N - 1][1], count[N - 1][1])
);
};
int lo = 0;
int hi = 0;
for(int i = 0; i < N; i++)
hi += abs(A[i]);
hi *= 2;
// c(lambda_hatt) >= K
// c(lo) >= K
// c(hi) < K
while(lo < hi - 1){
int mid = (lo + hi) / 2;
auto [sum_penalty, intervals] = solve_lambda(mid);
if(intervals >= K){
lo = mid;
}else{
hi = mid;
}
}
auto [vlambda, clambda] = solve_lambda(lo);
cout<<vlambda + K * lo<<endl;
}
