CodeEff/ECCO huggingface dataset:
# Original solution
o=lambda:list(map(int,input().split()))
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if ~l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print(a)


# Optimized solution
o=lambda:list(map(int,input().split()))
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
for _ in [0]*(n-1):a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1]
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if not l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print(a)
# Original solution
import sys
input = sys.stdin.readline
n,k = list(map(int,input().split()))
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)


# Optimized solution
import sys
#input = sys.stdin.readline
n,k = list(map(int,input().split()))
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)
# Original solution
import sys
stdin = sys.stdin

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

def bfs(graph:list, start:int) -> list:
    # 未探索のノードは距離null
    node = len(graph)
    dist = [None]*node
    
    # 始点ノードの距離を0とし、bfsのためのqueueを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    while que:
        cost, cur_node = que.popleft()

        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] is not None:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist

# 入力, グラフ作成
n,k = li()
adj_list = [[] for _ in range(n)]
edges = []
for _ in range(n-1):
    a,b = li_()
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    edges.append((a,b))

ans = n
# kが奇数の時
if k%2:
    for a,b in edges:
        dist1 = bfs(adj_list, a)
        dist2 = bfs(adj_list, b)
        ans = min(ans, sum([min(d1,d2) > (k-1)//2 for d1,d2 in zip(dist1, dist2)]))
    
# kが偶数の時
else:
    for st in range(n):
        dist = bfs(adj_list, st)
        ans = min(ans, sum([d > k//2 for d in dist]))

print(ans)

# Optimized solution
import sys
stdin = sys.stdin

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque
from collections import defaultdict

def bfs(graph:list, start:int) -> list:
    # 未探索のノードは距離null
    node = len(graph)
    dist = [None]*node
    
    # 始点ノードの距離を0とし、bfsのためのqueueを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    # kより大きいの距離のものを数える
    while que:
        cost, cur_node = que.popleft()

        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] is not None:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist
  
# 入力, グラフ作成
n,k = li()
adj_list = [[] for _ in range(n)]
edges = []
for _ in range(n-1):
    a,b = li_()
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    edges.append((a,b))

ans = n
# kが奇数の時
if k%2:
    for a,b in edges:
        dist1 = bfs(adj_list, a)
        dist2 = bfs(adj_list, b)
        ans = min(ans, sum([min(d1,d2) > (k-1)//2 for d1,d2 in zip(dist1, dist2)]))
    
# kが偶数の時
else:
    for st in range(n):
        dist = bfs(adj_list, st)
        ans = min(ans, sum([d > k//2 for d in dist]))

print(ans)
# Original solution
from collections import deque
def rad_reach(bfr,h,rest,E):
	cnt = 0
	Q = deque([(bfr,h,rest)])
	while Q:
		cnt += 1
		bfr,h,rest = Q.popleft()
		if rest > 0:
			for nxt in E[h]:
				if nxt == bfr:
					continue
				Q.append((h,nxt,rest-1))
	return cnt
def solve():
	N,K = list(map(int,input().split()))
	pairs = []
	E = [[] for i in range(N)]
	for i in range(N-1):
		p = [int(x)-1 for x in input().split()]
		pairs.append(p)
		E[p[0]].append(p[1])
		E[p[1]].append(p[0])
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in range(N):
			ans = min(ans,N-rad_reach(-1,c,rad,E))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(c2,c1,rad,E)-rad_reach(c1,c2,rad,E))
	print(ans)
solve()

# Optimized solution
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == b:
				continue
			cnt += rad_reach(h,nxt,dist+1,E,rad) 
	return cnt
def solve():
	N,K = list(map(int,input().split()))
	pairs = []
	E = [[] for i in range(N)]
	for i in range(N-1):
		a,b = [int(x)-1 for x in input().split()]
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in range(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(c2,c1,0,E,rad)-rad_reach(c1,c2,0,E,rad))
	print(ans)
solve()
# Original solution
from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<k//2:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

# Optimized solution
from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k>n//2:
	for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	f(k//2)
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)
# Original solution
def main():
    n, k = list(map(int, input().split()))
    a = []
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        a.append((u, v))
        g[u].append(v)
        g[v].append(u)
    st = []
    pu = st.append
    po = st.pop
    ans = 0
    if k % 2:
        k = k / 2 + 1
        for u, v in a:
            c = 0
            pu((u, k, v))
            pu((v, k, u))
            while st:
                u, d, p = po()
                d -= 1
                c += 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
            if ans < c:
                ans = c
    else:
        k = k / 2 + 1
        for i in range(n):
            c = 0
            pu((i, k, -1))
            while c < len(st):
                u, d, p = st[c]
                d -= 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
                c += 1
            if ans < c:
                ans = c
            del st[:]
    print(n - ans)
main()


# Optimized solution
def main(le=len):
    n, k = list(map(int, input().split()))
    a = []
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        a.append((u, v))
        g[u].append(v)
        g[v].append(u)
    st = []
    pu = st.append
    po = st.pop
    ans = 0
    if k % 2:
        k = k / 2 + 1
        for u, v in a:
            c = 0
            pu((u, k, v))
            pu((v, k, u))
            while c < le(st):
                u, d, p = st[c]
                d -= 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
                c += 1
            if ans < c:
                ans = c
            del st[:]
    else:
        k = k / 2 + 1
        for i in range(n):
            c = 0
            pu((i, k, -1))
            while c < le(st):
                u, d, p = st[c]
                d -= 1
                if d:
                    for v in g[u]:
                        if v != p:
                            pu((v, d, u))
                c += 1
            if ans < c:
                ans = c
            del st[:]
    print(n - ans)
main()
# Original solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
H = [0]+list(map(int, input().split()))
dp = [[[10**18]*(N+1) for _ in range(K+1)] for _ in range(2)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(K+1):
        for k in range(N+1):
            dp[(i+1)%2][j][k] = 10**18
            
    for j in range(K+1):
        for k in range(N+1):
            if j+1<=K:
                dp[(i+1)%2][j+1][k] = min(dp[(i+1)%2][j+1][k], dp[i%2][j][k])
            
            dp[(i+1)%2][j][i+1] = min(dp[(i+1)%2][j][i+1], dp[i%2][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%2][i][j])
    
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
H = [0]+list(map(int, input().split()))
dp = [[10**18]*(N+1) for _ in range(N-K+1)]
dp[0][0] = 0

for i in range(N-K):
    for j in range(N+1):
        for k in range(j):
            dp[i+1][j] = min(dp[i+1][j], dp[i][k]+max(0, H[j]-H[k]))

print((min(dp[N-K])))
# Original solution
n,K=list(map(int,input().split()))
l=list(map(int,input().split()))
INF=float('inf')
dp=[[[] for j in range(K+1)] for i in range(n+1)]
dp[0][0]=[(0,0)]
for i,j in enumerate(l,1):
    a1,b1=dp[i-1][0][0]
    dp[i][0]=[(a1+max(0,j-b1),j)]
for i,j in enumerate(l,1):
    for k in range(1,min(K+1,i+1)):
        tl=[]
        for a1,b1 in dp[i-1][k]:
            tl.append((a1+max(0,j-b1),j))
        dp[i][k]=tl+dp[i-1][k-1]
a=dp[-1][-1]
a.sort()
print((a[0][0]))

# Optimized solution
n,K=list(map(int,input().split()))
l=list(map(int,input().split()))
INF=float('inf')
dp=[[[] for j in range(K+1)] for i in range(n+1)]
dp[0][0]=[(0,0)]
for i,j in enumerate(l,1):
    a1,b1=dp[i-1][0][0]
    dp[i][0]=[(a1+max(0,j-b1),j)]
for i,j in enumerate(l,1):
    for k in range(1,min(K+1,i+1)):
        tl=dp[i-1][k-1]
        for a1,b1 in dp[i-1][k]:
            tl.append((a1+max(0,j-b1),j))
        tl.sort(reverse=True)
        tl.append((-1,-1))
        x=0
        l1=[]
        while len(tl)-1>x:
            a1,b1=tl[x]
            l1.append(tl[x])
            x+=1
            while tl[x][0]==a1:
                x+=1
        dp[i][k]=l1
a=dp[-1][-1]
a.sort()
print((a[0][0]))
# Original solution
N,K= list(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.copy() 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]))



# Optimized solution
N,K= list(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]))
# Original solution
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):
        # print(dp[i])
        ans = min(ans, dp[i][N-K])
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
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):
        # print(dp[i])
        ans = min(ans, dp[i][N-K])
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
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):
        # print(dp[i])
        ans = min(ans, dp[i][N-K])
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, K = (int(i) for i in input().split())
    H = [0] + [int(i) for i in input().split()]
    # 1-indexed
    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**12]*(N-K+1) for _ in range(N+1)]

    for x in range(N+1):
        dp[x][1] = H[x]

    for y in range(2, N-K+1):
        for x in range(N+1):
            for i in range(1, x):
                dp[x][y] = min(dp[x][y], dp[i][y-1] + max(0, H[x] - H[i]))

    ans = dp[0][N-K]
    for i in range(1, N+1):
        ans = min(ans, dp[i][N-K])
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict

n, k = list(map(int, input().split()))
hhh = list(map(int, input().split()))
INF = 10 ** 18
dp = defaultdict(lambda: INF)
dp[0, 0] = 0
for h in hhh:
    ndp = defaultdict(lambda: INF)
    for (changed, prev_h), operate in list(dp.items()):
        if h == prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate)
        elif h > prev_h:
            ndp[changed, h] = min(ndp[changed, h], operate + h - prev_h)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
        else:
            ndp[changed, h] = min(ndp[changed, h], operate)
            if changed < k:
                ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate)
    dp = ndp
print((min(dp.values())))


# Optimized solution
from collections import defaultdict

n, k = list(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 list(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)
    # print(h)
    # print(dict(dp))
    # print(dict(ndp))
    dp = ndp
print((min(dp.values())))
# Original solution
n,k = list(map(int, input().split( )))
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    mn = min(mn,h[i])
    dp[i][0] = min(mn,h[i])

for i in range(n):##右端
    for j in range(i+1):#本数
        for t in range(i):#右から2番目,
            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, dp[i][n-k-1])
print(ans)


# Optimized solution
n,k = list(map(int, input().split( )))
if n==k:
    print((0))
    exit()
h = list(map(int, input().split( )))
#h = [0]+h#h[0]=0追加
inf = 10**15

dp = [[inf]*n for _ in range(n+1)] #dp[i][j]右端がi、j+1本残す
mn = h[0]
for i in range(n):
    #mn = min(mn,h[i])
    dp[i][0] = h[i]#min(mn,h[i])

for i in range(1,n):##右端
    for j in range(i+1):#本数
        for t in range(j-1,i):#右から2番目,
            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)
# Original solution
def main():
    n, K = list(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 = [[10**13]*l for _ in range(K+1)]
        t = [[i+j for i, j in zip(a, kk)] for kk in dp]
        min_s = [[dp[i][j] for j in range(l)] for i in range(K+1)]
        for i in range(K+1):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(min_s[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):
            dp2[i][dh] = min(dp2[i][dh], min(
                [dp[i][j]+max(h-s[j], 0) for j in range(l)]))
        dp = dp2
    print((min([min(i) for i in dp])))


main()


# Optimized solution
def main():
    n, K = list(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()
# Original solution
N, K = list(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):
  ans = min(ans, dp[N-i][K-i])
print(ans)

# Optimized solution
N, K = list(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)