#include <cstdlib>
#include <bitset>
#include <functional>
#include <utility>
#include <chrono>
#include <tuple>
#include <new>
#include <memory>
#include <climits>
#include <cfloat>
#include <cinttypes>
#include <exception>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>
#include <valarray>
#include <ios>
#include <istream>
#include <ostream>
#include <iostream>
#include <fstream>
#include <streambuf>
#include <cstdio>
#include <thread>
// #include <bits/stdc++.h>
using namespace std;
long long wartosci[1000005];
int n, k;
int licz;
long long akt_wyn;
pair<long long, int> dynamik[2][1000005]; // 0 nie wzialem, 1 wzialem
pair<long long, int> policz_dla_m(long long m)
{
dynamik[1][0] = {-1e18, 0};
for (int i = 1; i <= n; i++)
{
if (dynamik[0][i - 1].first > dynamik[1][i - 1].first)
dynamik[0][i] = dynamik[0][i - 1];
else if (dynamik[0][i - 1].first < dynamik[1][i - 1].first)
dynamik[0][i] = dynamik[1][i - 1];
else
dynamik[0][i] = (dynamik[0][i - 1].second > dynamik[1][i - 1].second ? dynamik[0][i - 1] : dynamik[1][i - 1]);
dynamik[1][i] = dynamik[0][i - 1];
dynamik[1][i].second++;
dynamik[1][i].first -= m;
if (dynamik[1][i - 1].first > dynamik[1][i].first || (dynamik[1][i - 1].first == dynamik[1][i].first && dynamik[1][i - 1].second > dynamik[1][i].second))
dynamik[1][i] = dynamik[1][i - 1];
dynamik[1][i].first += wartosci[i];
}
if (dynamik[0][n].first > dynamik[1][n].first)
return dynamik[0][n];
else if (dynamik[0][n].first < dynamik[1][n].first)
return dynamik[1][n];
else
return (dynamik[0][n].second > dynamik[1][n].second ? dynamik[0][n] : dynamik[1][n]);
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> wartosci[i];
long long l, p;
l = 0;
p = 1e17;
while (l < p)
{
long long akt_m = ((l + p) / 2) + 1;
auto para = policz_dla_m(akt_m);
tie(akt_wyn, licz) = para;
if (licz >= k)
l = akt_m;
else
p = akt_m - 1;
}
auto para = policz_dla_m(l);
tie(akt_wyn, licz) = para;
akt_wyn += ((long long)licz) * l;
cout << akt_wyn;
}
