/*
Dimash ne katai!!!
shnurok krash))
Serikbay777 tozhe krash))
*/
#include <bits/stdc++.h>
#define pll pair < long long , long long >
#define len(s) (long long)(s.size())
#define all(x) x.begin() , x.end()
#define pii pair < int , int >
#define pofik continue
#define int long long
#define pb push_back
#define ins insert
#define F first
#define S second
const long long N = 3e5 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-9;
using namespace std;
int T = 1;
int binpow(int a , int b){
if(!b) return 1;
int val = binpow(a , b / 2);
if(b % 2 == 0) return val * val % MOD;
else return val * val % MOD * a % MOD;
}
int n , k;
int a[N], pref[N];
pll check(long double lmd){
pair < long double , int > dp[n + 5];
for(int i = 1; i <= n; i++) dp[i] = {-inf , 0};
dp[0] = {0 , 0};
set < pair <long double , int > > st;
st.ins({0 , 0});
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
if(dp[i].F == (st.rbegin() -> first) + pref[i] - lmd) dp[i].S = min(dp[i].S , (st.rbegin() -> second) + 1);
else dp[i] = max(dp[i] , {(st.rbegin() -> first) + pref[i] - lmd , (st.rbegin() -> second) + 1});
st.ins({dp[i].F - pref[i] , dp[i].S});
}
return dp[n];
}
void solve(){
cin >> n >> k;
for(int i = 1 ; i <= n; i++){
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
int l = 0 , r = 1e14 , res = 0;
while(l <= r){
long double mid = (l + r) / 2;
if(check(mid).S >= k){
l = mid + 1;
res = mid;
}
else{
r = mid - 1;
}
}
cout << check(res).F + k * res;
}
signed main(){
// cin >> T;
for(int cas = 1; cas <= T; cas++){
// cout << "Case " << cas << ":\n";
solve();
}
}
/*
___ __ _
| \ | | _____ | | _
| |\ \ | | __ __ | __ \ | | (_)
| | \ \ | | | | | || | \_\__ _| | _
| | \ \ | | | | | || | / _` | | | |
| | \ \| | | |__| || | / (_| | | | |
|_| \___| |______||_| \_,__|_| |_|
Created by: Moldiyar Abay
*/
