#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 300001;
int arr[maxn];
int dp[maxn][2], counti[maxn][2]; // 0 = closed, 1 = open
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> arr[i];
int l = 0, r = 1e18;
while (l < r)
{
int cost = (l + r) / 2;
memset(counti, 0, sizeof counti);
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++)
{
dp[i + 1][0] = dp[i][0];
counti[i + 1][0] = counti[i][0];
if ((dp[i + 1][0] < dp[i][0] - cost + arr[i]) || (dp[i+1][0] == dp[i][0] - cost + arr[i] && counti[i+1][0] > counti[i][0] + 1))
{
dp[i + 1][0] = dp[i][0] - cost + arr[i];
counti[i + 1][0] = counti[i][0] + 1;
}
if ((dp[i + 1][0] < dp[i][1] - cost + arr[i]) || (dp[i + 1][0] == dp[i][1] - cost + arr[i] && counti[i + 1][0] > counti[i][1] + 1))
{
dp[i + 1][0] = dp[i][1] - cost + arr[i];
counti[i + 1][0] = counti[i][1] + 1;
}
dp[i + 1][1] = dp[i][0] + arr[i];
counti[i + 1][1] = counti[i][0];
if ((dp[i + 1][1] < dp[i][1] + arr[i]) || (dp[i + 1][1] == dp[i][1] + arr[i] && counti[i][1]<counti[i+1][1]))
{
dp[i + 1][1] = dp[i][1] + arr[i];
counti[i + 1][1] = counti[i][1];
}
}
if (counti[n][0] <= k)
r = cost;
else if (counti[n][0] > k)
l = cost + 1;
}
int cost = l;
for (int i = 0; i < n; i++)
{
dp[i + 1][0] = dp[i][0];
counti[i + 1][0] = counti[i][0];
if ((dp[i + 1][0] < dp[i][0] - cost + arr[i]) || (dp[i + 1][0] == dp[i][0] - cost + arr[i] && counti[i + 1][0] > counti[i][0] + 1))
{
dp[i + 1][0] = dp[i][0] - cost + arr[i];
counti[i + 1][0] = counti[i][0] + 1;
}
if ((dp[i + 1][0] < dp[i][1] - cost + arr[i]) || (dp[i + 1][0] == dp[i][1] - cost + arr[i] && counti[i + 1][0] > counti[i][1] + 1))
{
dp[i + 1][0] = dp[i][1] - cost + arr[i];
counti[i + 1][0] = counti[i][1] + 1;
}
dp[i + 1][1] = dp[i][0] + arr[i];
counti[i + 1][1] = counti[i][0];
if ((dp[i + 1][1] < dp[i][1] + arr[i]) || (dp[i + 1][1] == dp[i][1] + arr[i] && counti[i][1] < counti[i + 1][1]))
{
dp[i + 1][1] = dp[i][1] + arr[i];
counti[i + 1][1] = counti[i][1];
}
}
if (counti[n][0] <= k)
r = cost;
else if (counti[n][0] > k)
l = cost + 1;
cout << dp[n][0] + l * counti[n][0] << "\n";
}
