#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> pa;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define log __lg
#define upper upper_bound
#define lower lower_bound
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (((mask) >> (i)) & 1ll)
#define reset(a, val) memset(a, val, sizeof(a))
#define fu(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define int ll
constexpr int MOD = 1e9 + 7;
constexpr int mx = 3e5;
constexpr int maxn = 1 << 20;
constexpr int base = 311;
constexpr int box = 447;
constexpr int blockn = mx/box;
constexpr ld PI = acosl(-1);
constexpr int LOG = log(maxn);
constexpr ll inf = 1e18 + 173;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r){
return l + rd() % (r - l + 1);
}
template<typename T> inline bool maximize(T &res, const T &val){if (val > res){res = val; return true;} return false;}
template<typename T> inline bool minimize(T &res, const T &val){if (val < res){res = val; return true;} return false;}
template<typename T> inline T sqr(const T &val){return val * val;}
inline void add(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
inline void sub(int &a, int b){a -= b; if (a < 0) a += MOD;}
inline int mul(const int &a, const int &b){return 1ll * (a%MOD) * (b%MOD) % MOD;}
inline int lcm(const int &a, const int &b){return 1ll * a * b / gcd(a, b) % MOD;}
//#define linear
//#define Ckn
#ifdef linear
vector<int> prime;
vector<int> lpf;
void sieve(){
prime.assign(1, 2);
lpf.assign(maxn + 1, 2);
lpf[0] = lpf[1] = 1;
for (int i = 3; i <= maxn; i += 2){
if (lpf[i] == 2) prime.pb(lpf[i] = i);
for (int j = 0; j < (int)prime.size() && i * prime[j] <= maxn && prime[j] <= lpf[i]; ++j)
lpf[prime[j] * i] = prime[j];
}
}
#endif
#ifdef Ckn
int fact[mx + 5];
int invm[mx + 5];
int invf[mx + 5];
void pre(){
fact[1] = fact[0] = 1;
invm[1] = invm[0] = 1;
invf[1] = invf[0] = 1;
fu(i, 2, mx){
fact[i] = 1ll * fact[i - 1] * i % MOD;
invm[i] = MOD - 1ll * MOD / i * invm[MOD % i] % MOD;
invf[i] = 1ll * invf[i - 1] * invm[i] % MOD;
}
}
int C(int k, int n){
if (k > n || k < 0) return 0;
return 1ll * fact[n] * invf[k] % MOD * invf[n - k] % MOD;
}
#endif
int A[mx + 5];
pa dp[mx + 5][2];
void solve(){
int n, k;
cin >> n >> k;
fu(i, 1, n) cin >> A[i];
A[n + 1] = 0;
int l = -inf, r = inf;
while (r != l){
int mid = (l + r) >> 1;
dp[1][1] = {A[1] - mid, 1};
dp[1][0] = max(dp[1][1], {0, 0});
fu(i, 2, n){
dp[i][1] = max(dp[i - 1][1], {dp[i - 1][0].fi - mid, dp[i - 1][0].se + 1});
dp[i][1].fi += A[i];
dp[i][0] = max(dp[i][1], dp[i - 1][0]);
}
if (max(dp[n][1], dp[n][0]).se <= k) r = mid;
else l = mid + 1;
}
dp[1][1] = {A[1] - l, 1};
dp[1][0] = max(dp[1][1], {0, 0});
fu(i, 2, n){
dp[i][1] = max(dp[i - 1][1], {dp[i - 1][0].fi - l, dp[i - 1][0].se + 1});
dp[i][1].fi += A[i];
dp[i][0] = max(dp[i][1], dp[i - 1][0]);
}
cout << max(dp[n][1], dp[n][0]).fi + k * l;
}
signed main(){
#define name "Sherwin"
if (fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
#define name "graph"
if (fopen(name".INP", "r")){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
#ifdef linear
sieve();
#endif
#ifdef Ckn
pre();
#endif
int testcase = 1;
//cin >> testcase;
while (testcase--){
solve();
}
}
/*
/\__/\
(=^.^= )
(") (")_/
~~~-Sherwin-~~~
*/
