#include<bits/stdc++.h>
using namespace std;
void readInput()
{
}
void solve()
{
}
int a[100004],n,k,lef[100004],minn[100004],maxx[100004],dp[104][100004];
int INF=2e8;
stack<int> s;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
readInput();
solve();
cin>>n>>k;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int i=1; i<=n; i++)
{
minn[i]=INF;
maxx[i]=INF;
}
s.push(1);
int maxxx=0;
for(int i=1; i<=n; i++)
{
maxxx=max(maxxx,a[i]);
dp[1][i]=maxxx;
}
for(int i=2; i<=n; i++)
{
while(!s.empty())
{
if(a[s.top()]>a[i])
{
// dp[1][i]=a[s.top()];
lef[i]=s.top();
int c=min(maxx[s.top()],min(minn[i],dp[1][i]));
minn[i]=min(minn[i],min(dp[1][s.top()],maxx[s.top()]));
maxx[s.top()]=c;
break;
}
else
minn[i]=min(min(minn[i],minn[s.top()]),min(dp[1][s.top()],maxx[s.top()])),s.pop();
}
s.push(i);
//if(dp[1][i]==0) dp[1][i]=a[i];
}
dp[1][0]=INF;
for(int i=2; i<=k; i++)
{
dp[i][0]=INF;
for(int j=1; j<=n; j++)
{
dp[i][j]=dp[i][lef[j]];
dp[i][j]=min(dp[i][j],minn[j]+a[j]);
minn[j]=INF;
maxx[j]=INF;
}
while(!s.empty())
s.pop();
s.push(1);
for(int j=2; j<=n; j++)
{
while(!s.empty())
{
if(a[s.top()]>a[j])
{
// dp[1][i]=a[s.top()];
int c=min(maxx[s.top()],min(minn[j],dp[i][j]));
minn[j]=min(minn[j],min(dp[i][s.top()],maxx[s.top()]));
maxx[s.top()]=c;
break;
}
else
minn[j]=min(min(minn[j],minn[s.top()]),min(dp[i][s.top()],maxx[s.top()])),s.pop();
}
s.push(j);
//if(dp[1][i]==0) dp[1][i]=a[i];
}
}
cout<<dp[k][n];
}
