// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int inf = 1e18 + 9;
const int MAX = 2e5 + 5;
const int LOG = 20;
const int MOD = 998244353;
void solve(){
int n, k; cin >> n >> k;
int arr[n + 1];
for(int i = 1; i <= n; ++i){
cin >> arr[i];
}
int l = 0, r = 3e14 + 100;
int ans = -inf;
while(l <= r){
int pen = (l + r) / 2;
array<int, 2> dp[n + 1][2];
for(auto &a:dp) for(auto& b:a) b = {0, 0};
dp[0][1] = {-inf, 0};
for(int i = 1; i <= n; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max((array<int, 2>){dp[i - 1][1][0] + arr[i], dp[i - 1][1][1]},
(array<int, 2>){dp[i - 1][0][0] - pen + arr[i], dp[i - 1][0][1] + 1});
}
array<int, 2> mx = max(dp[n][0], dp[n][1]);
if(mx[1] >= k){
// cout << mx[1] << ' ' << pen << ' ' << mx[0] + pen * k << '\n';
ans = mx[0] + pen * k;
l = pen + 1;
}
else{
r = pen - 1;
}
}
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t){
t--;
solve();
}
}
