#include <bits/stdc++.h>
using namespace std;
pair<int64_t, int> testar_rota(int64_t lambda, int n, vector<int>& comidas){
int64_t melhor_atual = -1e17;
int64_t melhor_geral = 0;
int rotas_melhor = 0;
int rotas_atual = 0;
for(int i = 0; i < n; ++i){
int64_t comida = (int64_t)comidas[i];
int64_t nova_rota = melhor_geral + comida - lambda;
int64_t continuar = melhor_atual + comida;
if(nova_rota >= continuar){
melhor_atual = nova_rota;
rotas_atual = rotas_melhor + 1;
} else {
melhor_atual = continuar;
}
if(melhor_atual >= melhor_geral){
melhor_geral = melhor_atual;
rotas_melhor = rotas_atual;
}
}
return {melhor_geral, rotas_melhor};
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> comidas(n);
for(int i = 0; i < n; ++i){
cin >> comidas[i];
}
int64_t maximo_satisfacao = 0;
int64_t menor = 0, maior = 1e17;
while(menor <= maior){
int64_t custo = menor + (maior - menor) / 2;
pair<int64_t, int> res = testar_rota(custo, n, comidas);
if(res.second >= k){
maximo_satisfacao = res.first + (int64_t)k * custo;
menor = custo + 1;
} else {
maior = custo - 1;
}
}
cout << maximo_satisfacao << "\n";
return 0;
}//t
