#include<iostream>
#include<cstdio>
#include<cassert>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<vector> 
#include<cstring>
#include<string>
#include<map>
#include<set>

#define mp make_pair
#define scn second
#define frs first
#define pb push_back

#define NAME "dibbles"

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> pi;
const int P = 239017;
const ll INF = 1000000000ll * 1000000000;
const int MAX = 2000 + 10;



int name[MAX][MAX], f[MAX][MAX];
int n, a[MAX];
int was[MAX][MAX];
ll dp[MAX][MAX];
int k; 

int C = 1;
void get_name(int l, int r) {
	if (r < l)
		return;
	int y = f[l][r];        
	get_name (l, y - 1);
	get_name (y + 1, r);
	name[l][r] = C++;		
}
int cnt = 0;

ll go(int l, int r, int k, int d) {
	if (r < l)
		return k == 0 ? 0 : INF;
	int v = name[l][r];
	if (was[v][k])
		return dp[v][k];
	was[v][k] = 1;
	if (k == 0)
		return 0;
	if (r - l + 1 < k)
		return INF;
	ll ans = INF;	
	int y = f[l][r];
	int mxl = (y - 1) - l + 1;
	for (int i = 0; i <= mxl; ++i) 
		ans = min(ans, go(l, y - 1, i, a[y]) + go(y + 1, r, k - i - 1, a[y]) + a[y] - d), ++cnt; 
	return dp[v][k] = ans;
}



int main() {
    freopen(NAME ".in", "r", stdin); 
    freopen(NAME ".out", "w", stdout); 
    
    scanf("%d%d", &n, &k);
    assert(n <= 100 && k <= 100);
    for (int i = 0; i < n; ++i)
    	scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
    	int mn = i;
    	for (int j = i; j < n; ++j) {
    		if (a[j] < a[mn])
    			mn = j;
    		f[i][j] = mn;
    	}    		
   	}
   	for (int i = 0; i <= n; ++i)
   		for (int j = 1; j <= n; ++j)
   			dp[i][j] = INF;
	get_name(0, n - 1);
	int ans = 0;
	for (int i = 0; i <= n; ++i) 
		if (go (0, n - 1, i, 0) <= k)
			ans = i;
	printf("%d", ans);
    return 0;
}




