#include <bits/stdc++.h>
using namespace std ;
int readInt ()
{
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
int main()
{
int n , k ;
n = readInt() ;
k = readInt() ;
int arr[n+1] ;
for(int i = 1 ; i <= n ; ++i)
arr[i] = readInt() ;
int dp[n+1][k+1] ;
int chosen[n+1][k+1] ;
dp[0][1] = 0 ;
for(int i = 1 ; i <= n ; ++i)
dp[i][1] = max(arr[i] , dp[i-1][1]) , chosen[i][1] = dp[i][1];
for(int j = 2 ; j <= k ; ++j)
{
stack<int>s ;
for(int i = j ; i <= n ; ++i)
{
dp[i][j] = dp[i-1][j-1] + arr[i] ;
chosen[i][j] = arr[i] ;
while(s.size() > 0)
{
int idx = s.top() ;
if(arr[idx] <= arr[i])
{
if(dp[idx][j] - chosen[idx][j] + max(chosen[idx][j] , arr[i]) < dp[i][j])
{
dp[i][j] = dp[idx][j] - chosen[idx][j] + max(chosen[idx][j] , arr[i]) ;
}
s.pop() ;
}
else
break ;
}
if(s.size() > 0)
{
int idx = s.top() ;
if(dp[idx][j] < dp[i][j])
{
dp[i][j] = dp[idx][j] ;
chosen[i][j] = chosen[idx][j] ;
}
}
s.push(i) ;
}
}
printf("%d" , dp[n][k]) ;
return 0 ;
}
