/// Author :Nguyễn Thái Sơn -Ti20 -THPT chuyên Lương Thế Vinh
#include<bits/stdc++.h>
#define TASK "test"
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define ti20_ntson int main()
#define all(x) (x).begin(),(x).end()
#define vi vector<int>
#define vii pair<int,int>
#define forup(i,l,r) for (int i=l; i<=r; i++)
#define fordown(i,l,r) for (int i=l; i>=r; i--)
#define getbit(x, i) (((x) >> (i)) & 1)
#define vvi vector< vector <int >>
using namespace std;
const int mod = 1e9+7;
const int oo = 1e8;
const int maxN = 1e5+5;
int n,a[maxN];
int dp[105][maxN],k;
void nhap()
{
cin >> n >> k;
for (int i=1; i<=n; i++) cin >> a[i];
}
void solve()
{
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
for (int i =1; i<=n; i++)
dp[1][i] = max (dp[1][i-1],a[i]);
for (int i=2; i<=k; i++) {
stack < vii > S;
for (int j=i; j <= n; j++) {
int res = dp[i-1][j-1];
while (!S.empty() && a[S.top().second] <= a[j]) {
res = min(res, S.top().first);
S.pop();
}
dp[i][j] = min(dp[i][S.empty() ? 0 : S.top().second], res + a[j]);
// cout << i << " " << j << " " << dp[i][j] << endl;
cout << res << endl;
S.push({res,j});
}
}
cout << dp[k][n];
}
ti20_ntson
{
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
int T =1;
// cin >> T;
while (T--) {
nhap();
solve();
}
}
/*
input
4 5
2 3 4 5 56
outpt
4455
*/
