AtCoder Beginner Contest 145 - Laminate

We will create an artwork by painting black some squares in a white square grid with 10^9 rows and N columns.

The current plan is as follows: for the i-th column from the left, we will paint the H_i bottommost squares and will not paint the other squares in that column.

Before starting to work, you can choose at most K columns (possibly zero) and change the values of H_i for these columns to any integers of your choice between 0 and 10^9 (inclusive).

Different values can be chosen for different columns.

Then, you will create the modified artwork by repeating the following operation:

 - Choose one or more consecutive squares in one row and paint them black. (Squares already painted black can be painted again, but squares not to be painted according to the modified plan should not be painted.)
Find the minimum number of times you need to perform this operation.

-----Constraints-----
 - 1 \leq N \leq 300
 - 0 \leq K \leq N
 - 0 \leq H_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
H_1 H_2 ... H_N

-----Output-----
Print the minimum number of operations required.

-----Sample Input-----
4 1
2 3 4 1

-----Sample Output-----
3

For example, by changing the value of H_3 to 2, you can create the modified artwork by the following three operations:
 - Paint black the 1-st through 4-th squares from the left in the 1-st row from the bottom.
 - Paint black the 1-st through 3-rd squares from the left in the 2-nd row from the bottom.
 - Paint black the 2-nd square from the left in the 3-rd row from the bottom.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, k) = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	hh = h[i - 1]
	for j in range(1, n + 1):
		if j == 1:
			dp[i][j] = hh
		elif j <= i:
			if i >= 2:
				dp[i][j] = min((dp[ii][j - 1] + max(0, hh - (h[ii - 1] if ii >= 1 else 0)) for ii in range(1, i)))
			else:
				dp[i][j] = hh
		else:
			dp[i][j] = float('inf')
ans = min((min((dp[nn][kk] for kk in range(n - k, n + 1))) for nn in range(1, n + 1)))
print(ans)


def main():
	INF = 10 ** 12
	(N, K) = list(map(int, input().split()))
	H = list(map(int, input().split()))
	H = [0] + H
	dp = [[[INF for _ in range(K + 1)] for _ in range(K + 1)] for _ in range(N + 1)]
	dp[0][0][0] = 0
	for n in range(1, N + 1):
		for k in range(min(n, K) + 1):
			v = INF
			for l in range(k + 1):
				if l > 0:
					dp[n][k][l] = dp[n - 1][k - 1][l - 1]
				v = min(v, dp[n - 1][k][l] + max(0, H[n] - H[n - l - 1]))
			dp[n][k][0] = v
	ans = INF
	for k in range(K + 1):
		for l in range(k + 1):
			ans = min(ans, dp[N][k][l])
	print(ans)
main()


def main():
	(N, K) = (int(i) for i in input().split())
	H = [0] + [int(i) for i in input().split()]
	if N == K:
		return print(0)
	elif K == 0:
		ans = 0
		for i in range(N):
			ans += max(H[i + 1] - H[i], 0)
		return print(ans)
	dp = [[10 ** 10] * (N - K + 1) for i in range(N + 1)]
	dp[0][0] = 0
	for x in range(1, N + 1):
		for y in range(N - K + 1):
			for i in range(x):
				dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0, H[x] - H[i]))
	ans = 10 ** 10
	for i in range(N + 1):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


import numpy as np
(n, k) = map(int, input().split())
h = np.array(input().split(), dtype=np.int)
if k < n:
	dp = np.zeros((n - k, n), dtype=np.int)
	dp[0] = h
	for i in range(n - k - 1):
		for j in range(i + 1, n):
			dp[i + 1, j] = np.min(dp[i][i:j] + np.maximum(h[j] - h[i:j], 0))
	print(dp[n - k - 1, n - k - 1:].min())
else:
	print(0)


(N, K) = map(int, input().split())
H = [0] + [int(a) for a in input().split()]
X = [[1 << 100] * (N - K + 1) for _ in range(N + 1)]
X[0][0] = 0
for i in range(1, N + 1):
	for j in range(1, min(i + 1, N - K + 1)):
		X[i][j] = min([X[ii][j - 1] + max(H[i] - H[ii], 0) for ii in range(i)])
print(min([x[-1] for x in X]))


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
INF = float('inf')
dp = [[INF] * (N - K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for (i, h) in enumerate(H):
	if i == 0:
		continue
	for j in range(N - K, 0, -1):
		for k in range(i):
			c = max(0, h - H[k])
			dp[i][j] = min(dp[i][j], dp[k][j - 1] + c)
print(min((row[-1] for row in dp)))


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(n, k) = [int(i) for i in readline().split()]
a = [0] + [int(i) for i in readline().split()]
n += 1
INF = 10 ** 18
K = n - k - 1
dp = [[INF] * n for _ in range(K + 1)]
dp[0][0] = 0
for i in range(1, n):
	ndp = [c[:] for c in dp]
	for l in range(min(i, K)):
		for now in range(0, i):
			ndp[l + 1][i] = min(ndp[l + 1][i], ndp[l][now] + max(0, a[i] - a[now]))
	dp = ndp
print(min(dp[-1]))


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
dp = [[10 ** 100] * (N - K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for x in range(1, N + 1):
	for y in range(1, min(x + 1, N - K + 1)):
		dp[x][y] = min([dp[i][y - 1] + max(H[x] - H[i], 0) for i in range(x)])
print(min([dp[i][N - K] for i in range(N + 1)]))


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
N += 1
H = [0] + H
DP = [[float('inf')] * N for _ in range(N)]
DP[0][0] = 0
for i in range(1, N):
	DP[i][1] = H[i]
	for j in range(2, i + 1):
		for k in range(1, i):
			DP[i][j] = min(DP[i][j], DP[k][j - 1] + max(0, H[i] - H[k]))
ans = float('inf')
for i in range(N):
	ans = min(ans, DP[i][N - K - 1])
print(ans)


def solve(n, k, h_list):
	if k == n:
		return 0
	large = sum(h_list) + 1
	dp = [[large] * n for _ in range(n + 1)]
	dp[1][0] = h_list[0]
	for i in range(1, n):
		for s in range(2, n + 1):
			dp[s][i] = min([dp[s - 1][j] + max(0, h_list[i] - h_list[j]) for j in range(i)])
		dp[1][i] = h_list[i]
	return min(dp[n - k])

def main():
	(n, k) = map(int, input().split())
	h_list = list(map(int, input().split()))
	res = solve(n, k, h_list)
	print(res)

def test():
	assert solve(4, 1, [2, 3, 4, 1]) == 3
	assert solve(6, 2, [8, 6, 9, 1, 2, 1]) == 7
	assert solve(10, 0, [1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000, 1, 1000000000]) == 4999999996
main()


def solve():
	from sys import stdin
	f_i = stdin
	(N, K) = map(int, f_i.readline().split())
	H = tuple(map(int, f_i.readline().split()))
	if N == K:
		return 0
	dp1 = list(H)
	for i in range(1, N - K):
		dp2 = dp1[:i]
		for (x, H_x) in enumerate(H[i:], start=i):
			v = min((dp_j + max(0, H_x - H_j) for (dp_j, H_j) in zip(dp1[i - 1:x], H[i - 1:x])))
			dp2.append(v)
		dp1 = dp2
	return min(dp1[N - K - 1:])
print(solve())


(n, k) = map(int, input().split())
h = list(map(int, input().split())) + [0]
dp = [[[10 ** 12 for _ in range(n + 1)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for a in range(n):
	for b in range(k + 1):
		for c in range(a + 1):
			if b < k:
				dp[a + 1][b + 1][c] = min(dp[a + 1][b + 1][c], dp[a][b][c])
			dp[a + 1][b][a + 1] = min(dp[a + 1][b][a + 1], dp[a][b][c] + max(0, h[a] - h[c - 1]))
print(min(dp[n][k]))


from collections import defaultdict
(n, k) = map(int, input().split())
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda : INF)
dp[0] = 0
mask1 = (1 << 10) - 1
mask2 = (1 << 63) - 1 ^ mask1
for h in hhh:
	ndp = defaultdict(lambda : INF)
	h_key = h << 10
	for (changed_prev_h, operate) in dp.items():
		changed = changed_prev_h & mask1
		prev_h = changed_prev_h >> 10
		if h == prev_h:
			key = h_key + changed
			ndp[key] = min(ndp[key], operate)
		elif h > prev_h:
			key = h_key + changed
			ndp[key] = min(ndp[key], operate + h - prev_h)
			if changed < k:
				key = changed_prev_h + 1
				ndp[key] = min(ndp[key], operate)
		else:
			key = h_key + changed
			ndp[key] = min(ndp[key], operate)
			if changed < k:
				key = changed_prev_h + 1
				ndp[key] = min(ndp[key], operate)
	dp = ndp
print(min(dp.values()))


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
a = [0] + list(map(int, input().split()))
inf = 10 ** 12
dp = [[[inf] * (N + 1) for _ in range(K + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for j in range(K + 1):
		for k in range(N + 1):
			if dp[i][j][k] == inf:
				continue
			x = max(0, a[i + 1] - a[k])
			dp[i + 1][j][i + 1] = min(dp[i + 1][j][i + 1], dp[i][j][k] + x)
			if j < K:
				dp[i + 1][j + 1][k] = min(dp[i + 1][j][k], dp[i][j][k])
res = inf
for j in range(K + 1):
	res = min(res, min(dp[-1][j]))
print(res)


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split())) + [0]
dp = [[0] * (K + 2) for i in [0] * (N + 2)]
for i in range(1, N + 2):
	for j in range(K + 1):
		dp[i][j] = min([dp[i - k][j - k + 1] + max(0, H[i] - H[i - k]) for k in range(1, min(j + 1, i) + 1)])
print(dp[N + 1][K])


LI = lambda : list(map(int, input().split()))
(N, K) = LI()
H = LI()
INF = 10 ** 15

def main():
	h = [0] + H
	dp = [[INF] * (N + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for i in range(1, N + 1):
		for j in range(1, i + 1):
			v = INF
			for k in range(i):
				x = max(0, h[i] - h[k])
				v = min(v, dp[k][j - 1] + x)
			dp[i][j] = v
	ans = min([dp[i][N - K] for i in range(N - K, N + 1)])
	print(ans)
main()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, k) = map(int, input().split())
	H = [0] + list(map(int, input().split()))
	dp = [[INF] * (n - k + 1) for _ in range(n + 1)]
	dp[0][0] = 0
	for x in range(1, n + 1):
		for y in range(1, n - k + 1):
			dp[x][y] = min((dp[x0][y - 1] + max(0, H[x] - H[x0]) for x0 in range(x)))
	print(min(*(dp[x][n - k] for x in range(n + 1))))
resolve()


import sys, bisect
input = sys.stdin.readline
(n, k) = map(int, input().split())
h = list(map(int, input().split()))
hs = [0] + sorted(h)
if k == 0:
	res = h[0]
	for i in range(1, n):
		res += max(0, h[i] - h[i - 1])
	print(res)
	exit()
dp = [[[10 ** 12] * (n + 1) for i in range(k + 1)] for j in range(n)]
kk = bisect.bisect_left(hs, h[0])
dp[0][0][kk] = h[0]
dp[0][1][0] = 0
for i in range(1, n):
	kk = bisect.bisect_left(hs, h[i])
	for j in range(k + 1):
		tmp = 10 ** 12
		for l in range(n):
			tmp = min(tmp, dp[i - 1][j][l] + max(0, hs[kk] - hs[l]))
		dp[i][j][kk] = tmp
	for j in range(1, k + 1):
		for l in range(n):
			dp[i][j][l] = min(dp[i][j][l], dp[i - 1][j - 1][l])
res = 10 ** 12
for j in range(k + 1):
	for l in range(n):
		res = min(res, dp[-1][j][l])
print(res)


import numpy as np
(N, K) = map(int, input().split())
H = list(map(int, input().split()))
sortedH = np.hstack((np.zeros(1, dtype=np.int64), np.sort(H)))
dic = {}
for (i, h) in enumerate(sortedH):
	dic[h] = i
inf = 10 ** 15
dp = np.full((302, len(sortedH) + 1), inf, dtype=np.int64)
dp[0, 0] = 0
for (i, h) in enumerate(H):
	for k in range(i + 1, -1, -1):
		dp[k + 1] = np.minimum(dp[k + 1], dp[k])
		idx = dic[h]
		ma = np.min(dp[k][:idx] + h - sortedH[:idx])
		mb = np.min(dp[k][idx:])
		dp[k] = np.full(len(sortedH) + 1, inf, dtype=np.int64)
		dp[k][idx] = min(ma, mb)
print(np.min(dp[:K + 1]))


(N, K) = map(int, input().split())
H = [0] + [int(i) for i in input().split()]
dp = [[float('inf')] * (N - K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
	for j in range(N - K + 1):
		dp[i][j] = min((dp[k][j - 1] + max(0, H[i] - H[k]) for k in range(i)))
print(min((dp[i][N - K] for i in range(N + 1))))


inpl = lambda : list(map(int, input().split()))
(N, K) = inpl()
H = [0] + inpl() + [0]
dp = [[0] * (K + 1) for _ in range(N + 2)]
for n in range(1, N + 2):
	for k in range(K + 1):
		if k >= n - 1:
			dp[n][k] = H[n]
		else:
			dp[n][k] = min((dp[n - 1 - l][k - l] + max(0, H[n] - H[n - 1 - l]) for l in range(k + 1)))
print(dp[-1][-1])


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K) = MAP()
M = N - K
A = [0] + LIST()
dp = list2d(M + 1, N + 1, INF)
dp[0][0] = 0
for i in range(1, M + 1):
	for (j, h1) in enumerate(A):
		for k in range(max(j - N, 0), j):
			h2 = A[k]
			dp[i][j] = min(dp[i][j], dp[i - 1][k] + max(h1 - h2, 0))
print(min(dp[M]))


(n, m) = list(map(int, input().split()))
if n == m:
	print(0)
	exit()
h = list(map(int, input().split()))
maxi = sum(h)
f = [e for e in h]
for i in range(n - m - 1):
	for j in range(n - 1, i, -1):
		res = maxi
		for k in range(i, j):
			res = min(res, f[k] + max(0, h[j] - h[k]))
		f[j] = res
print(min(f[n - m - 1:]))


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(n, k) = na()
h = na()
ys = h[:] + [0]
ys.sort()
ys2 = []
for v in ys:
	if len(ys2) > 0 and ys2[-1] == v:
		continue
	ys2.append(v)
ys = ys2
m = len(ys)
dp = [[999999999999999999] * m for _ in range(k + 1)]
dp[0][0] = 0
for v in h:
	ndp = [[999999999999999999] * m for _ in range(k + 1)]
	for i in range(k + 1):
		plus = 99999999999999999
		for j in range(m):
			plus = min(plus + (ys[j] - ys[j - 1] if j > 0 else 0), dp[i][j])
			if ys[j] == v:
				ndp[i][j] = min(ndp[i][j], plus)
			elif i + 1 <= k:
				ndp[i + 1][j] = min(ndp[i + 1][j], plus)
		plus = 99999999999999999
		for j in range(m - 1, -1, -1):
			plus = min(plus, dp[i][j])
			if ys[j] == v:
				ndp[i][j] = min(ndp[i][j], plus)
			elif i + 1 <= k:
				ndp[i + 1][j] = min(ndp[i + 1][j], plus)
	dp = ndp
ans = min((min(row) for row in dp))
print(ans)


def main():
	import sys
	input = sys.stdin.buffer.readline
	(N, K) = (int(i) for i in input().split())
	H = [0] + [int(i) for i in input().split()]
	if N == K:
		return print(0)
	elif K == 0:
		ans = 0
		for i in range(N):
			ans += max(H[i + 1] - H[i], 0)
		return print(ans)
	dp = [[10 ** 10] * (N - K + 1) for i in range(N + 1)]
	dp[0][0] = 0
	for (i, h) in enumerate(H):
		if i == 0:
			continue
		dp[i][1] = h
	for i in range(1, N + 1):
		for j in range(1, N - K + 1):
			for x in range(1, i):
				dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i] - H[x]))
	ans = 10 ** 10
	for i in range(N + 1):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	(n, k) = LI()
	h = LI()
	h.insert(0, 0)
	dp = [[float('inf')] * (n + 1) for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(n):
		ni = i + 1
		hi = h[ni]
		for s in range(n):
			ns = s + 1
			for j in range(ni):
				hj = h[j]
				nd = dp[j][s] + max(0, hi - hj)
				if nd < dp[ni][ns]:
					dp[ni][ns] = nd
	ans = min([dp[i][n - k] for i in range(n + 1)])
	print(ans)
	return
solve()


import sys
input = sys.stdin.readline

def max2(x, y):
	return x if x > y else y

def min2(x, y):
	return x if x < y else y
(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
dp = [[10 ** 9 * N for _ in range(N - K + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for (i, h) in enumerate(H[1:], start=1):
	for k in range(1, min2(i + 1, N - K + 1)):
		dp[i][k] = min((dp[j][k - 1] + max2(0, h - H[j]) for j in range(i)))
print(min((d[-1] for d in dp)))


def main():
	(n, K) = map(int, input().split())
	H = list(map(int, input().split()))
	s = sorted(set(H + [0]))
	d = {i: j for (j, i) in enumerate(s)}
	l = len(s)
	m = max(s)
	a = [m - i for i in s]
	dp = [[10 ** 13] * l for _ in range(K + 1)]
	dp[0][0] = 0
	for h in H:
		dh = d[h]
		dp2 = [[0] * l for _ in range(K + 1)]
		dp2[0] = [10 ** 13] * l
		t = [[0] * l for _ in range(K)]
		for i in range(K):
			for j in range(l):
				t[i][j] = dp[i][j] + a[j]
		min_s = [[10 ** 13] * l for i in range(K + 1)]
		for i in range(K):
			for j in range(l - 2, -1, -1):
				min_s[i][j] = min(dp[i][j + 1], min_s[i][j])
			for j in range(1, l):
				t[i][j] = min(t[i][j - 1], t[i][j])
			for j in range(l):
				t[i][j] = t[i][j] - a[j]
		for i in range(K):
			for j in range(l):
				dp2[i + 1][j] = min(min_s[i][j], t[i][j])
		for i in range(K + 1):
			temp = 10 ** 13
			for j in range(l):
				temp = min(temp, dp[i][j] + max(h - s[j], 0))
			dp2[i][dh] = min(dp2[i][dh], temp)
		dp = dp2
	print(min([min(i) for i in dp]))
main()


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1

def main():
	(N, K) = map(int, input().split())
	N += 1
	H = [0] + list(map(int, input().split())) + [0]
	dp = [[INF] * (K + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for i in range(N):
		for j in range(K + 1):
			for k in range(j, K + 1):
				if i - (k - j) >= 0:
					dp[i + 1][k] = min(dp[i + 1][k], dp[i - (k - j)][j] + max(H[i + 1] - H[i - (k - j)], 0))
					pass
	print(dp[-1][-1])
main()


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
dp = [[[10 ** 18] * (N + 1) for _ in range(K + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for j in range(K + 1):
		for k in range(N + 1):
			if j + 1 <= K:
				dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k])
			dp[i + 1][j][i + 1] = min(dp[i + 1][j][i + 1], dp[i][j][k] + max(0, H[i + 1] - H[k]))
ans = 10 ** 18
for i in range(K + 1):
	for j in range(N + 1):
		ans = min(ans, dp[N][i][j])
print(ans)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	(N, K) = MI()
	H = [0] + LI()
	N += 1
	inf = 10 ** 12
	dp = [[inf] * N for _ in range(N)]
	dp[0][0] = 0
	for i in range(1, N):
		for j in range(N):
			temp = inf
			for k in range(i):
				temp = min(temp, dp[k][j - 1] + max(0, H[i] - H[k]))
			dp[i][j] = temp
	ans = inf
	for i in range(N):
		ans = min(ans, dp[i][N - K - 1])
	print(ans)
main()


def solve():
	INF = 10 ** 12

	def max2(x, y):
		return x if x >= y else y

	def min2(x, y):
		return x if x <= y else y
	(N, K) = map(int, input().split())
	Hs = [0] + list(map(int, input().split()))
	dp = [[INF] * (N + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for i in range(1, N + 1):
		H = Hs[i]
		diffs = []
		for iPrev in range(i):
			diff = max2(0, H - Hs[iPrev])
			diffs.append(diff)
		dp[i][0] = 0
		dp[i][1] = H
		for j in range(2, min(i, N - K) + 1):
			for iPrev in range(i):
				dp[i][j] = min2(dp[i][j], dp[iPrev][j - 1] + diffs[iPrev])
	ans = min((dpi[N - K] for dpi in dp))
	print(ans)
solve()


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split())) + [0]
dp = [[float('inf') for i in range(K + 1)] for j in range(N + 2)]
dp[0] = [0 for i in range(K + 1)]

def cost(i, j):
	return max(0, H[j] - H[i])
for i in range(1, N + 2):
	for j in range(K + 1):
		for d in range(j + 1):
			if i - d - 1 < 0:
				break
			dp[i][j] = min(dp[i][j], cost(i - d - 1, i) + dp[i - d - 1][j - d])
print(dp[-1][K])


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [[10 ** 12] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for x in range(N + 1):
	for y in range(1, N + 1):
		for z in range(x):
			dp[x][y] = min(dp[x][y], dp[z][y - 1] + max(H[x] - H[z], 0))
ans = 10 ** 12
for x in range(N + 1):
	ans = min(dp[x][N - K], ans)
print(ans)


(N, K) = map(int, input().split())
H = list(map(int, [0] + input().split() + [0]))
d = [[10 ** 18] * (K + 1) for _ in range(N + 2)]
for i in range(K + 1):
	d[0][i] = 0
for hi in range(N + 1):
	hi += 1
	h = H[hi]
	for i in range(min(K + 1, hi)):
		for k in range(i + 1):
			d[hi][i] = min(d[hi][i], d[hi - k - 1][i - k] + max(H[hi - k - 1] - h, 0))
print(min(d[-1]))


def main():
	(N, K) = (int(i) for i in input().split())
	H = [0] + [int(i) for i in input().split()]
	if N == K:
		return print(0)
	elif K == 0:
		ans = 0
		for i in range(N):
			ans += max(H[i + 1] - H[i], 0)
		return print(ans)
	dp = [[10 ** 10] * (N - K + 1) for i in range(N + 1)]
	dp[0][0] = 0
	for (i, h) in enumerate(H):
		if i == 0:
			continue
		dp[i][1] = h
	for i in range(1, N + 1):
		for j in range(1, N - K + 1):
			for x in range(1, i):
				dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i] - H[x]))
	ans = 10 ** 10
	for i in range(N + 1):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	(n, k) = LI()
	a = LI()
	c = collections.defaultdict(lambda : inf)
	c[0, 0] = 0
	for t in a:
		nc = collections.defaultdict(lambda : inf)
		for (ck, cv) in c.items():
			(k1, k2) = ck
			if k1 >= t:
				if nc[t, k2] > cv:
					nc[t, k2] = cv
			elif nc[t, k2] > cv + t - k1:
				nc[t, k2] = cv + t - k1
			if k2 < k:
				if nc[k1, k2 + 1] > cv:
					nc[k1, k2 + 1] = cv
		c = nc
	return min(c.values())
print(main())


import sys
(N, K) = map(int, input().split())
if N == K:
	print(0)
	sys.exit()
H = list(map(int, input().split()))
dp = [[None] * (N - K + 1) for i in range(N)]
for i in range(N):
	nh = H[i]
	dp[i][1] = nh
	for j in range(i):
		for k in range(N - K):
			if dp[j][k] != None:
				if dp[i][k + 1] == None:
					dp[i][k + 1] = dp[j][k] + max(0, H[i] - H[j])
				else:
					dp[i][k + 1] = min(dp[i][k + 1], dp[j][k] + max(0, H[i] - H[j]))
ans = float('inf')
for i in range(N):
	if dp[i][-1] != None:
		ans = min(ans, dp[i][-1])
print(ans)


def main():
	(n, K) = map(int, input().split())
	h = list(map(int, input().split()))
	DP = [[float('inf')] * (K + 1) for i in range(K + 1)]
	DP[0][0] = 0
	for i in range(n):
		hi = h[i]
		nxt = [[float('inf')] * (K + 1) for i in range(K + 1)]
		for j in range(min(i + 1, K + 1)):
			for k in range(j + 1):
				l = i - k - 1
				if l < 0:
					left = 0
				else:
					left = h[l]
				a = hi - left if left < hi else 0
				nxt[j][0] = min(nxt[j][0], DP[j][k] + a)
				if j == K:
					continue
				nxt[j + 1][k + 1] = min(nxt[j + 1][k + 1], DP[j][k])
		DP = nxt
	ans = float('inf')
	for i in DP:
		ans = min(ans, min(i))
	print(ans)
main()


import sys
input = sys.stdin.readline
INF = 10 ** 18
(N, K) = map(int, input().split())
A = [0] + list(map(int, input().split())) + [0]
dp = [[INF] * (K + 1) for _ in range(N + 2)]
dp[0][0] = 0
for i in range(1, N + 2):
	for k in range(K + 1):
		tmp = INF
		for j in range(max(0, i - k - 1), i):
			tmp = min(tmp, dp[j][k - (i - j - 1)] + max(0, A[i] - A[j]))
		dp[i][k] = tmp
print(min(dp[-1]))


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
HSorted = sorted(H)
HIndexToHeight = []
HHeightToIndex = {}
for i in range(N):
	if i != 0 and HSorted[i] == HSorted[i - 1]:
		continue
	HIndexToHeight.append(HSorted[i])
	HHeightToIndex[HSorted[i]] = len(HIndexToHeight) - 1
INF = 10 ** 12
heightCount = len(HIndexToHeight)
DP = []
for i in range(N):
	DP.append([])
	for j in range(K + 1):
		DP[i].append([])
		for k in range(heightCount):
			DP[i][j].append(INF)
for k in range(heightCount):
	if k == HHeightToIndex[H[0]]:
		DP[0][0][k] = H[0]
	elif K != 0:
		DP[0][1][k] = HIndexToHeight[k]
for i in range(1, N):
	currentHeight = HHeightToIndex[H[i]]
	for j in range(K + 1):
		for k in range(heightCount):
			if currentHeight > k:
				if j > 0:
					DP[i][j][k] = min(DP[i - 1][j - 1][k], DP[i][j][k])
				DP[i][j][currentHeight] = min(DP[i - 1][j][k] + HIndexToHeight[currentHeight] - HIndexToHeight[k], DP[i][j][currentHeight])
			elif currentHeight == k:
				DP[i][j][currentHeight] = min(DP[i - 1][j][k], DP[i][j][currentHeight])
			else:
				if j > 0:
					DP[i][j][k] = min(DP[i - 1][j - 1][k], DP[i][j][k])
				DP[i][j][currentHeight] = min(DP[i - 1][j][k], DP[i][j][currentHeight])
ans = INF
for j in range(K + 1):
	for k in range(heightCount):
		if ans > DP[N - 1][j][k]:
			ans = DP[N - 1][j][k]
if K == N:
	print(0)
else:
	print(ans)


(n, k) = map(int, input().split())
h = list(map(int, input().split()))
if n == k:
	print(0)
	exit()
inf = 10 ** 15 * (n + 1)
dp = [[inf] * (n - k + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n - k + 1):
		if j == 1:
			dp[i][j] = h[i - 1]
		else:
			tmp = inf
			for l in range(1, i):
				tmp = min(tmp, dp[l][j - 1] + max(0, h[i - 1] - h[l - 1]))
			dp[i][j] = tmp
ans = inf
for i in range(n + 1):
	ans = min(ans, dp[i][-1])
print(ans)


def main():
	(N, K) = map(int, input().split())
	H = [0] + [int(x) for x in input().split()]
	DP = [[-1 for _ in range(K + 1)] for _ in range(N + 1)]
	DP[0] = [0 for _ in range(K + 1)]
	for i in range(1, N + 1):
		for j in range(K + 1):
			for k in range(max(i - j - 1, 0), i):
				previous = DP[k][j - (i - k - 1)]
				if previous == -1:
					continue
				if DP[i][j] == -1 or previous + max(H[i] - H[k], 0) < DP[i][j]:
					DP[i][j] = previous + max(H[i] - H[k], 0)
				if j > 0 and DP[i][j - 1] != -1 and (DP[i][j - 1] < DP[i][j]):
					DP[i][j] = DP[i][j - 1]
	ans = -1
	for i in range(N + 1):
		if K < N - i:
			continue
		if ans == -1 or DP[i][min(K - (N - i), K)] < ans:
			ans = DP[i][min(K - (N - i), K)]
	print(ans)
main()


def main():
	import numpy as np
	(n, k) = list(map(int, input().split()))
	H = list(map(int, input().split()))
	s = np.array(sorted(set(H + [0])), dtype=np.int64)
	d = {i: j for (j, i) in enumerate(s)}
	l = len(s)
	dp = np.full((k + 1, l), 10 ** 13, dtype=np.int64)
	dp2 = np.zeros((k + 1, l), dtype=np.int64)
	dp[0, 0] = 0
	for h in H:
		dh = d[h]
		dp2 = np.zeros((k + 1, l), dtype=np.int64)
		dp2[0] = np.full(l, 10 ** 13, dtype=np.int64)
		dp2[1:, :] = dp[:-1, :]
		temp = np.min(dp + np.concatenate([(h - s)[:dh], np.zeros(l - dh, dtype=np.int64)]), axis=1)
		dp2[:, dh] = np.minimum(dp2[:, dh], temp[:])
		dp = dp2
	print(np.min(dp))
main()


def examA():
	N = DI() / dec(7)
	ans = N
	print(N)
	return

def examB():
	ans = 0
	print(ans)
	return

def examC():
	ans = 0
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	(N, K) = LI()
	H = LI()
	H.insert(0, 0)
	dp = [[[inf] * (K + 1) for _ in range(N + 1)] for _ in range(N + 1)]
	dp[0][0][0] = 0
	for i in range(N):
		for j in range(i + 1):
			for k in range(K + 1):
				dp[i + 1][i + 1][k] = min(dp[i + 1][i + 1][k], dp[i][j][k] + max(0, H[i + 1] - H[j]))
				if k < K:
					dp[i + 1][j][k + 1] = min(dp[i + 1][j][k + 1], dp[i][j][k])
	ans = inf
	for j in range(N + 1):
		ans = min(ans, dp[-1][j][-1])
	print(ans)
	return
from decimal import getcontext, Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
getcontext().prec = 28
sys.setrecursionlimit(10 ** 7)
examF()


import numpy as np
INF = 10 ** 15

def solve(n, k, h):
	dp = np.full((n + 1, n + 1), INF, dtype=int)
	dp[0, 0] = 0
	h = np.array([0] + h, dtype=int)
	for (i, h_i) in enumerate(h[1:], 1):
		t = np.maximum(h_i - h[:i], 0)
		dp[i, 1:] = np.min(dp[:i, :-1] + t[:, None], axis=0)
	return np.min(dp[:, n - k])
(n, k) = map(int, input().split())
h = list(map(int, input().split()))
print(solve(n, k, h))


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
H = [0] + H
dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
	for j in range(1, N + 1):
		for x in range(i):
			dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i] - H[x]))
ans = float('inf')
for i in range(N + 1):
	ans = min(ans, dp[i][max(0, N - K)])
print(ans)


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
G = [0]
G.extend(H[:])
dp = [[0] * (N + 1) for i in range(N - K + 1)]
tempa = 0
if K < N - 1:
	for jtemp in range(N):
		j = jtemp + 1
		dp[1][j] = G[j]
	for itemp in range(N - K - 1):
		i = itemp + 2
		for jtemp in range(N - (i - 1)):
			j = jtemp + i
			temp = int(N * 1000000000.0)
			for ktemp in range(j - (i - 1)):
				k = ktemp + i - 1
				val = G[j] - G[k]
				if val < 0:
					val = 0
				if temp > dp[i - 1][k] + val:
					temp = dp[i - 1][k] + val
			dp[i][j] = temp
	tempa = dp[N - K][-1]
	for jtemp in range(N):
		j = jtemp + 1
		if tempa > dp[N - K][j] and dp[N - K][j] != 0:
			tempa = dp[N - K][j]
elif N - K == 1:
	tempa = min(H[:])
else:
	tempa = 0
print(tempa)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
(n, k) = LI()
h = [0] + LI()
dp = [[inf] * (n - k + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n - k + 1):
		for l in range(i):
			dp[i][j] = min(dp[i][j], dp[l][j - 1] + max(0, h[i] - h[l]))
ans = inf
for i in range(n + 1):
	ans = min(ans, dp[i][n - k])
print(ans)


def solve():
	INF = float('inf')

	def max2(x, y):
		return x if x >= y else y
	(N, K) = map(int, input().split())
	Hs = [0] + list(map(int, input().split()))
	if N == K:
		return 0
	dp = [INF] * (N + 1)
	dp[0] = 0
	for j in range(1, N - K + 1):
		dp2 = [INF] * (N + 1)
		for (i, H) in enumerate(Hs[j:], j):
			for k in range(j - 1, i):
				dp2[i] = min(dp2[i], dp[k] + max2(0, H - Hs[k]))
		dp = dp2
	return min(dp)
ans = solve()
print(ans)


def f_laminate(INF=float('inf')):
	(N, K) = map(int, input().split())
	H = [0] + list(map(int, input().split()))
	dp = [[INF] * (N - K + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for x in range(1, N + 1):
		for y in range(1, N - K + 1):
			for i in range(x):
				dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0, H[x] - H[i]))
	ans = INF
	for i in range(N + 1):
		ans = min(ans, dp[i][N - K])
	return ans
print(f_laminate())


import sys
(N, K) = map(int, input().split())
H = list(map(int, input().split()))
if N <= K:
	print(0)
	sys.exit()
dp = [[[float('inf')] * (K + 2) for i in range(N + 2)] for j in range(N + 1)]
dp[0][0][0] = H[0]
dp[0][-1][1] = 0
for i in range(N - 1):
	for j in range(i + 1):
		for k in range(K + 1):
			if H[j] > H[i + 1]:
				dp[i + 1][j][k + 1] = min(dp[i][j][k], dp[i + 1][j][k + 1])
				dp[i + 1][i + 1][k] = min(dp[i][j][k], dp[i + 1][i + 1][k])
			else:
				dp[i + 1][i + 1][k] = min(dp[i + 1][i + 1][k], dp[i][j][k] + H[i + 1] - H[j])
				dp[i + 1][j][k + 1] = min(dp[i][j][k], dp[i + 1][j][k + 1])
	for k in range(K):
		dp[i + 1][-1][k + 1] = min(dp[i][-1][k], dp[i + 1][-1][k + 1])
		dp[i + 1][i + 1][k] = min(dp[i + 1][i + 1][k], dp[i][-1][k] + H[i + 1])
ans = float('inf')
for i in range(K + 1):
	res = min((dp[N - 1][j][i] for j in range(N)))
	ans = min(ans, res)
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split())) + [0]
DP = [[1 << 60] * (K + 1) for i in range(N + 2)]
for k in range(K + 1):
	DP[0][k] = 0
for i in range(1, N + 2):
	for k in range(K + 1):
		for j in range(k + 1):
			DP[i][k] = min(DP[i][k], DP[i - j - 1][k - j] + max(0, H[i] - H[i - j - 1]))
print(min(DP[-1]))


import sys
input = sys.stdin.buffer.readline

def main():
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	H = [0] + H
	INF = 10 ** 15
	dp = [INF] * (N + 1)
	dp[0] = 0
	for i in range(N - K):
		use = [INF] * (N + 1)
		for j in range(i, N + 1):
			for k in range(j + 1, N + 1):
				use[k] = min(use[k], dp[j] + max(0, H[k] - H[j]))
		dp = use
	print(min(dp))
main()


(N, K) = map(int, input().split())
h = list(map(int, input().split()))
dp = [[float('inf') for j in range(N + 1)] for k in range(N)]
for j in range(N):
	dp[j][1] = h[j]
	dp[j][0] = 0
for i in range(1, N):
	for j in range(2, N + 1):
		dp[i][j] = min((dp[k][j - 1] + (h[i] - h[k]) * (h[i] >= h[k]) for k in range(i)))
test1 = min((dp[i][N - K] for i in range(N)))
print(test1)


(N, K) = map(int, input().split())
H = list(map(int, input().split()))

def dpinit(ps, val=0):
	res = [val for i in [0] * ps[-1]]
	for i in ps[:-1][::-1]:
		res = [res[:] for k in [0] * i]
	return res
H = [0] + H + [0]
dp = dpinit((N + 2, K + 2))
for i in range(1, N + 2):
	for j in range(K + 1):
		l = min(j + 1, i)
		cand = [dp[i - k][j - k + 1] + max(0, H[i] - H[i - k]) for k in range(1, l + 1)]
		dp[i][j] = min(cand)
print(dp[N + 1][K])


(N, K) = map(int, input().split())
H = list(map(int, input().split()))
if N <= K:
	print(0)
	exit()
dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for (i, h) in enumerate(H, start=1):
	dp[i][1] = h
for i in range(1, N + 1):
	for j in range(2, N + 1):
		for x in range(1, i):
			dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i - 1] - H[x - 1]))
ans = float('inf')
for i in range(N + 1):
	ans = min(ans, dp[i][max(0, N - K)])
print(ans)


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
INF = 10 ** 12
dp = [[INF] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for x in range(1, N + 1):
	dp[x][0] = 0
	dp[x][1] = H[x]
	for y in range(2, x + 1):
		for i in range(x):
			dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0, H[x] - H[i]))
ans = INF
for i in range(N + 1):
	ans = min(ans, dp[i][N - K])
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007

def POW(x, y):
	return pow(x, y, DVSR)

def INV(x, m=DVSR):
	return pow(x, m - 2, m)

def DIV(x, y, m=DVSR):
	return x * INV(y, m) % m

def LI():
	return [int(x) for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LS():
	return input().split()

def II():
	return int(input())

def FLIST(n):
	res = [1]
	for i in range(1, n + 1):
		res.append(res[i - 1] * i % DVSR)
	return res
(N, K) = LI()
MP = [0] + LI()
LG = 10 ** 15
DP = [[LG] * (N + 1) for i in range(N - K + 2)]
for i in range(1, N + 1):
	DP[0][i] = 0
	DP[1][i] = MP[i]
for i in range(1, N - K):
	for j in range(1, N + 1):
		for k in range(1, j):
			DP[i + 1][j] = min(DP[i + 1][j], DP[i][k] + max(0, MP[j] - MP[k]))
res = 10 ** 15
for i in range(1, N + 1):
	res = min(res, DP[N - K][i])
print(res)


(N, K) = map(int, input().split())
H = list(map(int, input().split())) + [0]
dp = [[10 ** 12] * (K + 2) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(min(i + 1, K) + 1):
		for k in range(j + 1):
			dp[i + 1][j] = min(dp[i + 1][j], dp[i - k][j - k] + max(H[i] - H[i - k - 1], 0))
ans = min(dp[-1])
for i in range(K + 1):
	ans = min(ans, dp[N - i][K - i])
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def main():
	inf = 10 ** 16
	(n, k) = map(int, input().split())
	hh = [0] + list(map(int, input().split()))
	dp = [[0] * (k + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		h = hh[i]
		for j in range(k + 1):
			v = inf
			for nd in range(k + 1):
				if i - 1 - nd < 0 or j - nd < 0:
					break
				v = min(v, dp[i - 1 - nd][j - nd] + max(0, h - hh[i - 1 - nd]))
			dp[i][j] = v
	print(min((dp[n - d][k - d] for d in range(min(n + 1, k + 1)))))
main()


INF = float('inf')
(N, K, *H) = map(int, open(0).read().split())
H = [0] + H
if N == K:
	print(0)
	quit()
dp = [0] + [INF] * N
for i in range(1, N - K + 1):
	dp = [INF] * i + [min((dp[k] + max(0, h - H[k]) for k in range(i - 1, j))) for (j, h) in enumerate(H[i:], i)]
print(min(dp))


(n, K) = map(int, input().split())
a = [0] + list(map(int, input().split())) + [0]
INF = float('inf')
n += 1
dp = [[[INF for i in range(K + 1)] for j in range(n + 1)] for k in range(n + 1)]
dp[0][0][0] = 0
mx = 0
for i in range(1, n + 1):
	x = a[i]
	for j in range(i):
		for k in range(1, min(K, i) + 1):
			dp[i][j][k] = dp[i - 1][j][k - 1]
	for k in range(min(K, i) + 1):
		for l in range(1, i + 1):
			dp[i][i][k] = min(dp[i][i][k], dp[i - 1][i - l][k] + max(0, x - a[i - l]))
print(dp[n][n][K])


(n, K) = map(int, input().split())
h = list(map(int, input().split()))
h = [0] + h
INF = 1001001001001
dp = [[INF] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0
for j in range(n):
	for i in range(1, n + 1):
		for k in range(i):
			dp[i][j + 1] = min(dp[i][j + 1], dp[k][j] + max(0, h[i] - h[k]))
ans = INF
for i in range(n + 1):
	ans = min(ans, dp[i][n - K])
print(ans)


(n, k) = map(int, input().split())
H = [0] + list(map(int, input().split()))
m = n - k
DP = [[float('inf')] * (m + 1) for _ in range(n + 1)]
DP[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if i < j:
			continue
		DP[i][j] = min((DP[k][j - 1] + max(0, H[i] - H[k]) for k in range(i)))
print(min((DP[i][m] for i in range(n + 1))))


ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
(n, K) = mi()
hlis = li()
inf = 10 ** 13 + 7
dp = [[inf] * n for _ in range(n)]
for i in range(n):
	dp[0][i] = hlis[i]
for i in range(1, n):
	for k in range(i, n):
		for l in range(k):
			dp[i][k] = min(dp[i][k], dp[i - 1][l] + max(0, hlis[k] - hlis[l]))
tukau = n - K
ans = inf
if K == n:
	print(0)
	exit()
for i in range(tukau - 1, n):
	ans = min(ans, dp[tukau - 1][i])
print(ans)


(n, k) = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0, 0)
dp = [[float('inf')] * (n - k + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n - k + 1):
		now = float('inf')
		for l in range(i):
			now = min(dp[l][j - 1] + max(0, h[i] - h[l]), now)
		dp[i][j] = now
ans = float('inf')
for i in range(1, n + 1):
	ans = min(ans, dp[i][n - k])
print(ans if n > k else 0)


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	(N, K) = map(int, readline().split())
	H = [0] + list(map(int, readline().split())) + [0]
	dp = [[INF] * (N + 1) for _ in range(N + 1)]
	for i in range(N + 1):
		dp[i][0] = 0
	for i in range(1, N + 1):
		dp[i][1] = H[i]
		for j in range(2, i + 1):
			for k in range(1, i):
				dp[i][j] = min(dp[i][j], dp[k][j - 1] + max(0, H[i] - H[k]))
	ans = INF
	for i in range(1, N + 1):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


import math
import sys
(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split()))
if K == 0:
	ans = 0
	pre = 0
	for h in H:
		ans += max(0, h - pre)
		pre = h
	print(ans)
	sys.exit()
dp = [[math.inf] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
	for j in range(i):
		for k in range(K + 1):
			dp[i][k] = min(dp[j][k] + max(0, H[i] - H[j]), dp[i][k])
	for j in range(i):
		for k in range(K - 1, -1, -1):
			dp[j][k + 1] = dp[j][k]
		dp[j][0] = math.inf
ans = math.inf
for i in range(N + 1):
	ans = min(ans, min(dp[i]))
print(ans)


(N, K) = map(int, input().split())
H = [0] + list(map(int, input().split())) + [0]
N += 1
inf = 10 ** 18
dp = [[inf] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for (i, h) in enumerate(H[1:], 1):
	for j in range(K + 1):
		for k in range(K + 1):
			if i - k - 1 < 0 or j - k < 0:
				continue
			h_p = H[i - k - 1]
			dp[i][j] = min(dp[i][j], dp[i - k - 1][j - k] + max(0, h - h_p))
print(min(dp[-1]))


(N, K) = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [[10 ** 13] * N for _ in range(N)]
dp[0][0] = H[0]
for i in range(1, N):
	for j in range(i + 1):
		if j == 0:
			dp[i][j] = H[i]
			continue
		for k in range(i):
			dp[i][j] = min(dp[i][j], dp[k][j - 1] + max(0, H[i] - H[k]))
if N == K:
	ans = 0
else:
	ans = 10 ** 13
	for i in range(N):
		ans = min(ans, dp[i][N - K - 1])
print(ans)


(n, k) = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 18
k = n - k
dp = [[INF] * (k + 1) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(k):
		if j == 0:
			dp[i + 1][j + 1] = min(dp[0][j] + h[i], dp[i + 1][j + 1])
			continue
		for last_i in range(i):
			if last_i + 1 < j:
				continue
			dp[i + 1][j + 1] = min(dp[last_i + 1][j] + max(h[i] - h[last_i], 0), dp[i + 1][j + 1])
ans = 10 ** 18
for i in range(n + 1):
	ans = min(dp[i][k], ans)
print(ans)


(n, k) = map(int, input().split())
dp = []
for i in range(n + 2):
	dp.append([])
	for j in range(n + 2):
		dp[-1].append([])
		for l in range(k + 1):
			dp[-1][-1].append(10 ** 12)
for l in range(k + 1):
	dp[0][0][l] = 0
h = list(map(int, input().split()))
h.append(0)
h.reverse()
h.append(0)
h.reverse()
for i in range(1, n + 2):
	for j in range(n + 2):
		for l in range(k + 1):
			dp[i][i][l] = min(dp[i][i][l], dp[i - 1][j][l] + max(0, h[i] - h[j]))
			if l > 0:
				dp[i][j][l] = min(dp[i][j][l], dp[i - 1][j][l - 1])
				dp[i][0][l] = min(dp[i][0][l], dp[i - 1][j][l - 1] + h[j])
ans = dp[n + 1][0][0]
for j in range(n + 2):
	for l in range(k + 1):
		ans = min(ans, dp[n + 1][j][l])
print(ans)


def main():
	(n, k) = map(int, input().split())
	tmp = list(map(int, input().split()))
	h = [0]
	for v in tmp:
		h.append(v)
	dp = [[float('inf')] * (n - k + 1) for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(1, n + 1):
		for j in range(1, n - k + 1):
			tmp = float('inf')
			for l in range(i):
				p = max(0, h[i] - h[l])
				if tmp > dp[l][j - 1] + p:
					tmp = dp[l][j - 1] + p
			dp[i][j] = tmp
	ans = float('inf')
	for i in range(n + 1):
		if ans > dp[i][n - k]:
			ans = dp[i][n - k]
	print(ans)
main()


def main():
	(N, K) = map(int, input().split())
	H = [0] + list(map(int, input().split()))
	dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for i in range(1, N + 1):
		for j in range(i):
			diff = max(H[i] - H[j], 0)
			for k in range(min(N - K, j + 1)):
				dp[i][k + 1] = min(dp[i][k + 1], dp[j][k] + diff)
	ans = float('inf')
	for i in range(N + 1):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


(n, k) = map(int, input().split())
if n == k:
	print(0)
	exit()
h = list(map(int, input().split()))
inf = 10 ** 15
dp = [[inf] * n for _ in range(n + 1)]
mn = h[0]
for i in range(n):
	dp[i][0] = h[i]
for i in range(1, n):
	for j in range(i + 1):
		for t in range(j - 1, i):
			dp[i][j] = min(dp[i][j], dp[t][j - 1] + max(h[i] - h[t], 0))
ans = inf
for i in range(n):
	ans = min(ans, min(dp[i][n - k - 1:]))
print(ans)


import os
import sys
from collections import defaultdict
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K) = list(map(int, sys.stdin.readline().split()))
H = list(map(int, sys.stdin.readline().split()))
if K == N:
	print(0)
	exit()
dp = [[defaultdict(lambda : INF) for _ in range(K + 2)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
	for k in range(K + 1):
		for (h, cnt) in dp[i][k].items():
			dp[i + 1][k][H[i]] = min(dp[i + 1][k][H[i]], cnt + max(0, H[i] - h))
			dp[i + 1][k + 1][h] = min(dp[i + 1][k + 1][h], dp[i][k][h])
ans = min(dp[-1][K].values())
print(int(ans))


INF = 10 ** 15
(N, K) = map(int, input().split())
Hs = [0] + list(map(int, input().split())) + [0]
dp = [[INF] * (K + 1) for _ in range(N + 2)]
dp[0][0] = 0
for n in range(1, N + 2):
	for k in range(K + 1):
		for l in range(1, min(n, k + 1) + 1):
			dp[n][k] = min(dp[n][k], dp[n - l][k - l + 1] + max(0, Hs[n] - Hs[n - l]))
print(dp[N + 1][K])


(n, k) = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
inf = 10 ** 13
dp = [[0] * (k + 1)]
for i in range(1, n + 2):
	dp.append([inf] * (k + 1))
	for j in range(i):
		for u in range(i - j - 1, k + 1):
			dp[-1][u] = min(dp[-1][u], dp[j][u - i + j + 1] + max(h[i] - h[j], 0))
print(min(dp[-1]))


import numpy as np
(n, k) = list(map(int, input().split()))
hhh = list(map(int, input().split()))
hhh = np.array([0] + hhh, dtype=np.int64)
INF = 10 ** 18
dp = np.full((n + 1, k + 1), fill_value=INF, dtype=np.int64)
dp[0, 0] = 0
for (i, h) in enumerate(hhh[1:], start=1):
	ndp = np.full((n + 1, k + 1), fill_value=INF, dtype=np.int64)
	ndp[:n, 1:] = dp[:n, :-1]
	ndp[i] = (dp + np.maximum(0, h - hhh)[:, np.newaxis]).min(axis=0)
	dp = ndp
print(dp.min())


(N, K) = map(int, input().split())
H = list(map(int, input().split())) + [0]
h = [0] * (N + 1)
h[0] = H[0]
for i in range(1, N):
	h[i] = max(H[i] - H[i - 1], h[i])
for i in range(1, N + 1):
	h[i] += h[i - 1]
data = [[0] * N for i in range(N)]
for L in range(N):
	for R in range(L, N):
		if L == 0:
			data[L][R] = h[-1] - h[R + 1] + H[R + 1]
		else:
			data[L][R] = h[L - 1] + h[-1] - h[R + 1] + max(0, H[R + 1] - H[L - 1])
for L in range(N):
	for R in range(L, N):
		data[L][R] = h[-1] - data[L][R]
dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(1, N + 1):
	for j in range(min(i + 1, K + 1)):
		dp[i][j] = dp[i - 1][j]
		for k in range(j - 1, -1, -1):
			if dp[i][j] < dp[i - 1 - j + k][k] + data[i - j + k][i - 1]:
				dp[i][j] = dp[i - 1 - j + k][k] + data[i - j + k][i - 1]
print(h[-1] - max(dp[N]))


(n, k) = map(int, input().split())
h = list(map(int, input().split()))
if k == n:
	print(0)
	exit()
dp = [[0 for _ in range(n)] for _ in range(n - k)]
dp[0] = [] + h
for x in range(1, n - k):
	for y in range(n):
		temp = float('inf')
		for i in range(y):
			temp = min(temp, dp[x - 1][i] + max(0, h[y] - h[i]))
		dp[x][y] = temp
print(min(dp[n - k - 1]))


import sys
input = sys.stdin.readline

def main():
	(n, k) = map(int, input().split())
	H = [0] + list(map(int, input().split()))
	DP = [[10 ** 12] * (n - k + 1) for _ in range(n + 1)]
	DP[0][0] = 0
	for x in range(1, n + 1):
		for y in range(1, n - k + 1):
			for i in range(x):
				DP[x][y] = min(DP[x][y], DP[i][y - 1] + max(0, H[x] - H[i]))
	print(min((DP[i][-1] for i in range(n + 1))))
main()


(n, k) = list(map(int, input().split()))
hs = [0] + list(map(int, input().split()))
max_val = sum([max(hs[i + 1] - hs[i], 0) for i in range(n)])
dp = [[max_val for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		dp[i][j] = min([dp[i - 1][l] + max(hs[j] - hs[l], 0) for l in range(j)])
print(min([dp[n - k][l] for l in range(n + 1)]))


def main():
	import sys
	input = sys.stdin.readline
	(N, K) = map(int, input().split())
	H = list(map(int, input().split()))
	H.append(0)
	H.insert(0, 0)
	N += 2
	inf = 10 ** 12
	dp = [[inf] * (K + 1) for _ in range(N)]
	dp[0][0] = 0
	for i in range(N):
		for k in range(K + 1):
			for j in range(K - k + 1):
				if i + j + 1 < N:
					dp[i + j + 1][k + j] = min(dp[i + j + 1][k + j], dp[i][k] + max(0, H[i + j + 1] - H[i]))
	print(min(dp[-1]))
main()


from functools import lru_cache
(n, k) = map(int, input().split())
h = [0] + list(map(int, input().split())) + [0]
INF = 10 ** 18

@lru_cache(maxsize=None)
def solve(i, nokori):
	if i == 0:
		return 0
	res = INF
	for j in range(nokori + 1):
		if i - 1 - j < 0:
			break
		diff = max(h[i] - h[i - 1 - j], 0)
		res = min(solve(i - 1 - j, nokori - j) + diff, res)
	return res
print(solve(n + 1, k))


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
inf = float('inf')
mod = 10 ** 9 + 7

def pprint(*A):
	for a in A:
		print(*a, sep='\n')

def INT_(n):
	return int(n) - 1

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [I() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	(N, K) = MI()
	H = LI()
	dp = [[0] + [inf] * N for _ in range(N)]
	for i in range(N):
		dp[i][1] = H[i]
	dp[0][1] = H[0]
	for right in range(N):
		for size in range(2, N + 1):
			for i in range(right):
				dp[right][size] = min(dp[right][size], dp[i][size - 1] + max(0, H[right] - H[i]))
	ans = inf
	for i in range(N):
		ans = min(ans, dp[i][N - K])
	print(ans)
main()


(N, K) = [int(s) for s in input().split(' ')]
H = [int(s) for s in input().split(' ')]
dp = [[] for _ in range(N)]
for (n, h) in enumerate(H):
	if n == 0:
		before = [{0: 0}] + [{} for _ in range(K)]
	else:
		before = dp[n - 1]
	dp[n] = [{}] + before[:-1]
	current = dp[n]
	for k in range(K + 1):
		for (h_before, count) in before[k].items():
			candidate = current[k].get(h, float('inf'))
			if h_before >= h:
				current[k][h] = min(candidate, count)
			else:
				current[k][h] = min(candidate, count + h - h_before)
print(min([v for d in dp[-1] for v in d.values()]))


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 13
(n, K) = [int(item) for item in input().split()]
h = [0] + [int(item) for item in input().split()]
dp = [[[INF] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for (i, item) in enumerate(h):
	if i == 0:
		dp[0][0][0] = 0
		continue
	for j in range(n - 1, -1, -1):
		for k in range(n - 1, -1, -1):
			if dp[i - 1][j][k] == INF:
				continue
			dp[i][j + 1][k] = min(dp[i][j + 1][k], dp[i - 1][j][k])
			dp[i][j][i] = min(dp[i][j][i], dp[i - 1][j][k] + max(0, h[i] - h[k]))
ans = INF
for j in range(n + 1):
	ans = min(ans, dp[n][K][j])
print(ans)


import sys
readline = sys.stdin.readline
(N, K) = map(int, readline().split())
H = list(map(int, readline().split()))
H = [0] + H
N += 1
inf = 10 ** 18
dp = [[[inf] * (K + 1) for j in range(N)] for i in range(N)]
dp[0][0][0] = 0
for i in range(1, N):
	hi = H[i]
	for j in range(i):
		hj = H[j]
		for k in range(1, 1 + min(K, i)):
			dp[i][j][k] = dp[i - 1][j][k - 1]
	for k in range(min(K + 1, i)):
		dp[i][i][k] = min((dp[i - 1][j][k] + max(0, hi - H[j]) for j in range(i)))
print(min((min(dp[N - 1][j]) for j in range(N))))


max2 = lambda x, y: x if x > y else y
min2 = lambda x, y: x if x < y else y

def solve(K, H):
	H = [0] + H + [0]
	N = len(H)
	dp = [[float('inf')] * (i + 1) for i in range(N)]
	dp[0] = [0]
	for (r, hr) in enumerate(H):
		for (l, hl) in enumerate(H[:r]):
			for k in range(l + 1):
				dp[r][k + (r - l - 1)] = min2(dp[r][k + (r - l - 1)], dp[l][k] + max2(0, hr - hl))
	return dp[-1][K]
(N, K) = map(int, input().split())
H = list(map(int, input().split()))
print(solve(K, H))


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
from copy import deepcopy

def solve():
	(n, k) = LI()
	h = [0] + LI()
	d = defaultdict(int)
	d[0, 0] = 0
	for i in range(1, n + 1):
		nd = defaultdict(lambda : inf)
		for (key, value) in d.items():
			(a, b) = key
			if nd[i, b] > value + (h[i] - h[a] if h[i] > h[a] else 0):
				nd[i, b] = value + (h[i] - h[a] if h[i] > h[a] else 0)
			if b + 1 > k:
				continue
			if nd[a, b + 1] > value:
				nd[a, b + 1] = value
		d = nd
	ans = inf
	for i in range(n + 1):
		for j in range(k + 1):
			ans = min(ans, d[i, j])
	print(ans)
	return
solve()