#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())
const ll INF = 1'000'000'000'000'000LL;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vll A(1+N, INF);
for(int i = 1; i <= N; i++) cin >> A[i];
ll* DP[1+K];
DP[0] = new ll[1+N];
DP[1] = new ll[1+N];
for(int k = 2; k <= K; k++)
{
DP[k] = DP[k-2];
}
for(int i = 1; i <= N; i++)
{
DP[0][i] = DP[1][i] = +INF;
}
DP[0][0] = 0;
for(int k = 1; k <= K; k++)
{
for(int i = 0; i < k; i++)
DP[k][i] = +INF;
for(int i = k; i <= N; i++)
{
DP[k][i] = +INF;
for(int i2 = k-1; i2 <= i-1; i2++)
{
ll mxv = 0;
for(int f = i2+1; f <= i; f++)
mxv = max(mxv, A[f]);
DP[k][i] = min(DP[k][i], mxv + DP[k-1][i2]);
}
}
}
cout << DP[K][N] << '\n';
}
