#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
const long long INF = -1e18; // Use a sufficiently small negative number for initialization
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// Compute prefix sums (0-based indexing for A, 1-based for prefix_sum)
// prefix_sum[i] = sum of a[0]...a[i-1]
vector<long long> prefix_sum(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix_sum[i + 1] = prefix_sum[i] + a[i];
}
// dp[i] will store the maximum satisfaction using the first i plates (0..i-1)
// with exactly j people (current iteration of j).
vector<long long> prev_dp(n + 1, 0); // Base case: 0 people, max sat is 0 for any number of plates
for (int j = 1; j <= k; ++j) {
vector<long long> current_dp(n + 1, INF);
current_dp[0] = 0; // 0 plates, j people assigned empty segments, max sat is 0.
long long max_val = INF; // This will store max_{0 <= p < i} (prev_dp[p] - prefix_sum[p])
for (int i = 1; i <= n; ++i) {
// When computing current_dp[i] (using plates 0..i-1) for j people:
// Option 1: j-th segment ends before plate i-1 (or is empty at i-1).
// Max satisfaction is current_dp[i-1].
current_dp[i] = current_dp[i - 1];
// Option 2: j-th segment ends exactly at plate i-1.
// It starts at some plate p (0 <= p <= i-1).
// Sum = a[p] + ... + a[i-1] = prefix_sum[i] - prefix_sum[p].
// Previous j-1 people used plates 0..p-1. Max sat is prev_dp[p].
// Total = prev_dp[p] + prefix_sum[i] - prefix_sum[p].
// We need max over 0 <= p <= i-1: max(prev_dp[p] - prefix_sum[p]) + prefix_sum[i].
// The term max(prev_dp[p] - prefix_sum[p]) needs to be calculated for p up to i-1.
// The required max_val for index i is max_{0 <= p <= i-1} (prev_dp[p] - prefix_sum[p]).
// This can be updated iteratively: max_{0 <= p <= i-1} = max(max_{0 <= p <= i-2}, prev_dp[i-1] - prefix_sum[i-1])
// Update max_val to include the term for index i-1: (prev_dp[i-1] - prefix_sum[i-1])
// This max_val will be used for calculating current_dp[i], maximizing over segments ending at i-1.
max_val = max(max_val, prev_dp[i-1] - prefix_sum[i-1]);
// If max_val was not INF, we can potentially end the j-th segment at i-1
if (max_val != INF) {
current_dp[i] = max(current_dp[i], max_val + prefix_sum[i]);
}
}
prev_dp = current_dp;
}
cout << prev_dp[n] << endl;
return 0;
}
