///Old is gold, and gold is great. So old is great!
/*
This bozo is cheating, plz ban him cfs!!!!!
bozo: top1severtin
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long int
#define eb emplace_back
#define ins insert
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define MASK(x) (1ll << x)
#define all(x) (x).begin(), (x).end()
#define all_rev(x) (x).rbegin(), (x).rend()
#define FOR(i, l, r) for(int i = (int)(l), _ = (int)(r); i <= _; i++)
#define FORD(i, l, r) for(int i = (int)(l), _ = (int)(r); i >= _; i--)
#define SFOR(i, l, r, x) for(int i = (int)(l), _ = (int)(r); i <= _; i += (x))
#define SFORD(i, l, r, x) for(int i = (int)(l), _ = (int)(r); i >= _; i -= (x))
#define db double
#define ldb long double
#define ms(x, val) memset(x, val, sizeof(x))
#define sp(x) setprecision(x) << fixed
#define ff first
#define ss second
#define rsz resize
#define el "\n"
#define coding24_7_simulator signed main(void)
#define div ______div
template<typename T> void debug_1d(const T& a, const string& name) {
if(a.empty()) {
cerr << name << " is empty!\n";
return;
}
FOR(i, 0, a.size() - 1) {
cerr << name << "[" << i << "]: " << a[i] << el;
}
}
template<typename T> void debug_2d(const T& a, const string& name) {
if(a.empty()) {
cerr << name << "is empty!\n";
return;
}
FOR(i, 0, a.size() - 1) {
if(a[i].empty()) {
cerr << name << "[" << i << "] is empty!\n";
continue;
}
FOR(j, 0, a[i].size() - 1) {
cerr << name << "[" << i << "]" << "[" << j << "]: " << a[i][j] << " ";
}
cerr << el;
}
}
template<typename T> void debug_var(const T& a, const string& name) {
cerr << name << ": " << a << el;
}
template<typename T> void debug_map(const T& a, const string& name) {
if(a.empty()) {
cerr << name << " is empty!\n";
return;
}
for(const auto& it : a) {
cerr << name << "[" << it.ff << "]: " << it.ss << el;
}
}
template<typename T> void debug_stack(stack<T> s, const string& name) {
if (s.empty()) {
cerr << name << " is empty!\n";
return;
}
int idx = 0;
while (!s.empty()) {
cerr << name << "[" << idx++ << "]: " << s.top() << '\n';
s.pop();
}
}
template<typename T> void debug_queue(queue<T> q, const string& name) {
if (q.empty()) {
cerr << name << " is empty!\n";
return;
}
int idx = 0;
while (!q.empty()) {
cerr << name << "[" << idx++ << "]: " << q.front() << '\n';
q.pop();
}
}
template<typename T> void debug_pq(priority_queue<T> pq, const string& name) {
if (pq.empty()) {
cerr << name << " is empty!\n";
return;
}
int idx = 0;
while (!pq.empty()) {
cerr << name << "[" << idx++ << "]: " << pq.top() << '\n';
pq.pop();
}
}
void read_file() {
#define NAME "txt"
freopen(NAME ".INP", "r", stdin);
freopen(NAME ".OUT", "w", stdout);
}
void ifndef_read_file(){
#define NAME2 "read"
#ifndef ONLINE_JUDGE
freopen(NAME2 ".INP", "r", stdin);
freopen(NAME2 ".OUT", "w", stdout);
#endif // ONLINE_JUDGE
}
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<vector<int>> vector2d_int;
typedef vector<vector<char>> vector2d_char;
const long long oo = 2e18;
const int oo_int = 2e9;
const int mod = 1e9 + 7;
const int mod998 = 998244353;
void prepare(){
}
const int N = 3e5 + 5;
int a[N], n, k;
struct Data{
int val, seg;
};
Data compare(const Data& a, const Data& b){
if(a.val != b.val) return (a.val > b.val) ? a : b;
return (a.seg < b.seg) ? a : b;
}
Data get(int lambda){
Data out{0, 0}, in{-oo, oo};
FOR(i, 1, n){
Data nxt_out = compare(out, in);
Data extend{in.val + a[i], in.seg};
Data start_in{out.val + a[i] - lambda, out.seg + 1};
Data nxt_in = compare(extend, start_in);
out = nxt_out;
in = nxt_in;
}
Data res = compare(out, in);
return res;
}
void solve() {
cin >> n >> k;
FOR(i, 1, n){
cin >> a[i];
}
int l = 0, r = 1e9 * n, ans = r;
while(l <= r){
int m = (l + r) >> 1;
auto [val, seg] = get(m);
if(seg <= k){
r = m - 1;
ans = m;
}
else l = m + 1;
}
auto [val, seg] = get(ans);
cout << val + k * ans << el;
}
coding24_7_simulator {
ios_base::sync_with_stdio(0);
cin.tie(0);
//read_file();
ifndef_read_file();
prepare();
int t = 1;
//cin >> t;
while(t--)
solve();
return 0;
}
