Harryxun/stf_run huggingface dataset:
# coding: utf-8

import codecs
import sys

sys.stdout = codecs.getwriter("shift_jis")(sys.stdout) # ??????
sys.stdin = codecs.getreader("shift_jis")(sys.stdin) # ??\???

# ??\??¬?????????print??????????????´?????? print(u'?????????') ??¨??????
# ??\??¬?????????input??? input(u'?????????') ??§OK
# ??°?¢???????????????????????????´??????6,7???????????????????????¢??????

DEBUG = 0

if DEBUG == 0:
	a = []
	for i in range(200):
		deglist=[int(x) for x in input().split(" ")]
		a.append(deglist)
else:
	a = [[5,7],[1,99],[1000,999]]

for i in range(len(a)):
	wa = a[i][0] + a[i][1]
	print len(str(wa))

"""
while True:
	try:
		deglist = [int(x) for x in input().split(" ")]
	except EOFError:
		break

"""

### FIXED CODE ###

# coding: utf-8

import codecs
import sys

sys.stdout = codecs.getwriter("shift_jis")(sys.stdout) # ??????
sys.stdin = codecs.getreader("shift_jis")(sys.stdin) # ??\???

# ??\??¬?????????print??????????????´?????? print(u'?????????') ??¨??????
# ??\??¬?????????input??? input(u'?????????') ??§OK
# ??°?¢???????????????????????????´??????6,7???????????????????????¢??????

"""
DEBUG = 0

if DEBUG == 0:
	a = []
	for i in range(200):
		deglist=[int(x) for x in input().split(" ")]
		a.append(deglist)
else:
	a = [[5,7],[1,99],[1000,999]]

for i in range(len(a)):
	wa = a[i][0] + a[i][1]
	print len(str(wa))
"""

while True:
	try:
		a,b = map(int, raw_input().split())
		print len(str(a+b))
	except EOFError:
		break
s = input()
k = int(input())
sub = set()
for i in range(len(s)):
  for j in range(1,k):
    sub.add(s[i:i+j])
print(sorted(list(sub))[k-1])

### FIXED CODE ###

s = input()
k = int(input())
sub = set()
for i in range(len(s)):
  for j in range(1,k+1):
    sub.add(s[i:i+j])
print(sorted(list(sub))[k-1])
a = int(input())
b = int(input())

print (a * b, 2 * a + 2 * b)

### FIXED CODE ###

import sys

(a, b) = map(int, input().split())

print (a * b, (a + b) * 2)
A, B, C, D, E, F = map(int, input().split())

density = 0
max_density = 0
ans = []
for a in range(31):
    if a*A*100> F:
        break
    for b in range(31):
        if a==0 and b==0:
            break
        if a*A*100+b*B*100>F:
            break
        for c in range(101):
            for d in range(101):
                if a*A*100+b*B*100*c*C+d*D>F:
                    break
#                 print(a*A*100 + b*B*100 + c*C + d*D)
                if ( a*A*100 + b*B*100 + c*C + d*D <= F ) and ( 100*(c*C+d*D)/(a*A*100 + b*B*100 + c*C + d*D) <= 100*E/(100+E) ):
                    density = 100*(c*C+d*D)/(a*A*100 + b*B*100 + c*C + d*D)
#                     print(density)
#                     print("{} {}".format(a*A*100+b*B*100, c*C+d*D))
                    if max_density < density:
#                         print(max_density)
                        max_density = density
                        ans.append("{} {}".format(a*A*100+b*B*100+c*C+d*D, c*C+d*D))
print(ans[-1])

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

density = 0
max_density = 0
ans = []
for a in range(31):
    if a*A*100> F:
        break
    for b in range(31):
        if a==0 and b==0:
            continue
        if a*A*100+b*B*100>F:
            break
        for c in range(101):
            for d in range(101):
                density = 100*(c*C+d*D)/(a*A*100 + b*B*100 + c*C + d*D)
#                 if c==0 and d==0 and max_density <= density:
#                     ans.append("{} {}".format(a*A*100+b*B*100+c*C+d*D, c*C+d*D))
                if a*A*100+b*B*100*c*C+d*D>F:
                    break
#                 print(a*A*100 + b*B*100 + c*C + d*D)
                if ( a*A*100 + b*B*100 + c*C + d*D <= F ) and ( 100*(c*C+d*D)/(a*A*100 + b*B*100 + c*C + d*D) <= 100*E/(100+E) ):
#                     print(density)
#                     print("{} {}".format(a*A*100+b*B*100, c*C+d*D))
                    if max_density <= density:
#                         print(max_density)
                        max_density = density
                        ans.append("{} {}".format(a*A*100+b*B*100+c*C+d*D, c*C+d*D))


print(ans[-1])
n=int(input())
a=[0 for i in range(n)]
for i in range(m): #0,1,
    if i%3!=0 and i%5!=0:
        a[i]=int(i+1)

print(sum(a))


### FIXED CODE ###

n=int(input())
a=[0 for i in range(n+1)]
for i in range(n+1): #0,1,2,3,…n-1,n+1-1:nが3でも5でも割り切れない場合range(n)ではダメ
    if i%3!=0 and i%5!=0:
        a[i]=int(i)

print(sum(a))
N = input()
a = map(int, raw_input().split())
a.sort()
print a[-1] - a[0]


### FIXED CODE ###

a = map(int, raw_input().split())
d = a[0] * 100 + a[1] * 10 + a[2]
if d % 4 == 0:
	print "YES"
else:
	print "NO"
a=input()

a=a.split()

x=a[0]
y=a[1]

c=x*y

print(c)

### FIXED CODE ###

a=input()

a=a.split()

A=int(a[0])
B=int(a[1])
C=A*B

print(C)
S = int(input())

DP = [0]*(S+1)
DP[0] = 0
DP[1] = 0
DP[2] = 0

for i in range(3, S + 1):
  DP[i] += 1
  for j in range(i - 3 + 1):
    DP[i] += DP[j]

print(DP[S] % (10 ** 9 + 7))


### FIXED CODE ###

S = int(input())

if S < 3:
  print(0)
  import sys
  sys.exit()

DP = [0]*(S+1)
DP[0] = 0
DP[1] = 0
DP[2] = 0

for i in range(3, S + 1):
  DP[i] += 1
  for j in range(i - 3 + 1):
    DP[i] += DP[j]

print(DP[S] % (10 ** 9 + 7))
N, M = map(int, input().split(" "))
A_list = []
B_list = []
total = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    A_list.append(A)
    B_list.append(B)

z = list(zip(A_list, B_list))
z.sort()

for a, b in z:
    if b > M:
        total += M * a
        break
    else:
        total += b * a
        M -= b

print(total)

### FIXED CODE ###

H, W = map(int, input().split(" "))
h, w = map(int, input().split(" "))

result = H * W - (h * W + w * (H - h))

print (result)
N=int(input())
A=list(map(int,input().split()))

B=[]
for i in range(N-1):
    B.append(min(A[i],A[i+1]))
B.append(A[-1])

print(sum(B))

### FIXED CODE ###

N = int(input())
B = list(map(int, input().split()))

A = []

for i in range(N):
	if i == 0:
		A.append(B[0])
	elif 1 <= i <= N-2:
		A.append(min(B[i],B[i-1]))
	else:
		A.append(B[-1])

print(sum(A))
a=65280; b=61680; c=52428; d=43690; e=65535
QS = [[] for i in range(17)]
QS[1] = [a, b, c, d]
L = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}
H = []
get = L.get
push = H.append
for l in range(1, 16):
    Q = QS[l]
    li = 13-l; l3 = l+3; l1 = l+1
    pop = Q.pop
    pushQN = QS[l1].append
    while Q:
        p = pop()
        if L[p] < l: continue
        if l < 13:
            if l1 < get(p ^ e, 17):
                L[p ^ e] = l1
                l < 12 and pushQN(p ^ e)
            for q, r in H:
                if r < li:
                    if l3+r < get(p & q, 17): L[p & q] = l3+r; QS[l3+r].append(p & q)
                    if l3+r < get(p ^ q, 17): L[p ^ q] = l3+r; QS[l3+r].append(p ^ q)
                elif r == li:
                    if p & q not in L: L[p & q] = 16
                    if p ^ q not in L: L[p ^ q] = 16
                else: break
            l < 7 and push((p, l))
        elif l1 < get(p ^ e, 17): L[p ^ e] = l1
print(*map(L.__getitem__, eval("e&"+",e&".join(open(0).read().replace(*"-~").replace(*"*&").replace(*"1e").split()[:-1]))),sep='\n')

### FIXED CODE ###

def make(n):
    C = {0: 0}
    for i in range(n):
        b = int(input(), 2)
        for k, v in dict(C).items():
            if C.get(k^b, 0) < v+1:
                C[k^b] = v+1
    return C
def calc(P, Q):
    yield 0
    for k, v in P.items():
        if k in Q:
            yield v + Q[k]
def solve():
    while 1:
        n, m = map(int, input().split())
        if n+m == 0:
            break
        yield max(calc(make(n//2), make(n-n//2)))
print(*solve(), sep="\n")
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.append(0)
a.sort(reverse=True)


def waru(i, tempb):
    a[i - 1] = a[i]
    a[i] = tempb

    if a[i] < a[i + 1]:
        waru(i + 1, tempb)


while m > 0:
    a[0] /= 2
    if a[0] < a[1]:
        waru(1, a[0])
    m -= 1

b = []
for i in a:
    b.append(math.floor(i))

print(sum(b))



### FIXED CODE ###

import heapq

n,m  = map(int,input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(m):
    tmax = heapq.heappop(a)
    tmax = -(-tmax //2)
    heapq.heappush(a,tmax)

print(-1*sum(a))
a

### FIXED CODE ###

H,W=map(int,input().split())
A=[]
for i in range(H):
  A.append(input())
#print(A)

sw=0
for i in range(H):
  tmp=0
  for j in range(W-1):
    if A[i][j]=="#" and A[i][j+1]==".":
      tmp=1
    if tmp==1 and A[i][j]=="." and A[i][j+1]=="#":
      sw=1
#print(sw)

if sw==1:
  print("Impossible")
else:
  l=[]
  r=[]
  for i in range(H):
    ll=0
    for j in range(W-1):
      if A[i][j]=="." and A[i][j+1]=="#":
        ll=j+1
        break
    l.append(ll)
    
    rr=W-1
    for j in range(W-1):
      if A[i][j]=="#" and A[i][j+1]==".":
        rr=j
        break
    r.append(rr)
#  print(l)
#  print(r)

  sw2=0
  for i in range(len(r)-1):
    if r[i]!=l[i+1]:
      sw2=1
  print("Impossible" if sw2==1 else "Possible")
N = int(input())
MOD = 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        t[i-1], t[i] = t[i], t[i-1]
        if 'AGC' in ''.join(t):
            return False
        else:
            return True
        
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1:
    ret = 0
    for c in "ATGC":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))



### FIXED CODE ###


N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N+1)]
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret
print(dfs(0, 'TTT'))
a, b, k = map(int,input().split())
n = list(range(a,b+1))
print(*sorted(set(n[:k]) | set(n[-k:])),sep="\n")

### FIXED CODE ###

a, b, k = map(int,input().split())
n = range(a,b+1)
print(*sorted(set(n[:k]) | set(n[-k:])),sep="\n")
ACGT = ['A', 'C', 'G', 'T']
S = input()
cnt = 0
max_cnt = 0
for s in S:
    if s in ACGT:
        cnt += 1
        cntList.append(cnt)
    else:
        max_cnt = max(cnt, max_cnt)
        cnt = 0
print(max_cnt)

### FIXED CODE ###

S = input()

ACGT = ['A', 'C', 'G', 'T']
cntList = []
cnt = 0
cntList.append(cnt)
for s in S:
    if s in ACGT:
        cnt += 1
        cntList.append(cnt)
    else:
        cnt = 0
print(max(cntList))
xa = list(map(int, input().split()))

if x < a:
  print(0)
else:
  print(10)


### FIXED CODE ###

xa = list(map(int, input().split()))

if xa[0] < xa[1]:
  print(0)
else:
  print(10)
a,b,c = map(int,input().split(" "))

if a==b and a==c:
	print(1)
	ptn = 1

if a==b and a!=c:
	print(1)
	ptn=2

cnt = 0

for i in range(a,b):
	if c%i == 0:
		cnt += 1

if ptn != 1 and ptn != 2:
	print(cnt)

### FIXED CODE ###

a,b,c = map(int,input().split(" "))

ptn = 0

if a==b and a==c:
	print(1)
	ptn = 1

if a==b and a!=c:
	if a < c:
		print(1)
		ptn=2
	else:
		print(0)
		ptn=2

cnt = 0

for i in range(a,b+1):
	if c%i == 0:
		cnt += 1

if ptn != 1 and ptn != 2:
	print(cnt)
n = int(input())
a = [int(e) for e in input().split()]
ans = 1
if 0 in a:
    print(0)
else:
for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        break  
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(e) for e in input().split()]
ans = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            print(-1)
            break  
    else:
        print(ans)
import math
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
now = A[0]
ans = 0
for i in range(1,N):
    now = (now*A[i])//math.gcd(now, A[i])
for i in range(N):
    ans += now//A[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

def prime_factors(n):
    d = {}
    while n%2 == 0:
        d[2] = d.get(2, 0) + 1
        n //= 2
    i = 3
    while i*i <= n:
        while n%i == 0:
            d[i] = d.get(i, 0) + 1
            n //= i
        i += 2
    if n > 2:
        d[n] = d.get(n, 0) + 1
    return d

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
G = {}
for a in A:
    pf = prime_factors(a)
    for k,v in pf.items():
        G[k] = max(G.get(k, 0), v)
lcm = 1
for k,v in G.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD) % MOD
    ans %= MOD
print(ans)
n = list(input())
l = len(n)

for i in range(l):
    n[i] = int(n[i])

score = 0

if l == 1:
    print(n[0])
else:
    if n.count(9) == l-1:
        if n[0] != 9:
            score += sum(n)
        else:
            score += 8 + 9*(l-1)
    else:
        if n[0] != 9:
            score += n[0]-1 + 9*(l-1)
        else:
            for j in range(n):
                if n[j] != 9:
                    n[j-1] = 8
                    score += 8 + 9*(n-1)
                    break
    print(score)

### FIXED CODE ###

n = list(input())
l = len(n)

for i in range(l):
    n[i] = int(n[i])

score = 0

if l == 1:
    print(n[0])
else:
    if n.count(9) == l:
        score = sum(n)
    elif n.count(9) == l-1:
        if n[0] != 9:
            score += sum(n)
        else:
            score += 8 + 9*(l-1)
    else:
        if n[0] != 9:
            score += n[0]-1 + 9*(l-1)
        else:
            for j in range(l):
                if n[j] != 9:
                    n[j-1] = 8
                    score += 8 + 9*(l-1)
                    break
    print(score)
# coding: utf-8

wether = input("Today's weather:")
if weather == "Sunny":
    print("Cloudy")
elif wether == "Cloudy":
    print("Rainy")
elif wether == "Rainy":
    print("Sunny")


### FIXED CODE ###

# coding: utf-8

weather = input()
if weather == "Sunny":
    print("Cloudy")
elif weather == "Cloudy":
    print("Rainy")
elif weather == "Rainy":
    print("Sunny")
n = input()
ans = ''
for i in n:
    if n[i] == '1':
        ans += '9'
    elif n[i] == '9':
        n[i] += '1'
    else:
        ans += n[i]
print(ans)

### FIXED CODE ###

n = input()
ans = []
for i in range(len(n)):
    if n[i] == '1':
        ans.append('9')
    elif n[i] == '9':
        ans.append('1')
    else:
        ans.append(n[i])
print(''.join(ans))
import math
def calc_pattern(stairs):
    d=stairs//2
    l=[(math.factorial(i+(d-i)*2)/math.factorial(i)/math.factorial((d-i)*2))%1000000007  for i in range(d+1)]
    return (sum(l))%1000000007

#stairs=10
#print(calc_pattern(stairs))

# if A[i]+1==A[i+1]: print(0) exit()
N,M=map(int,input().split())
#A=[int(input()) for n in range(M)]
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
#print(A)
# now=0, for a in A:
# 0~A[0]-1, A[0]+1~A[1]-1
# A の先頭に-1を入れれば、A[i]+1~A[i+1]-1 で統一できそう
s=1
for m in range(M+1):
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        #print("{} ~ {}".format(A[m]+1, A[m+1]-1))
        #print(calc_pattern(A[m+1]-1 - (A[m]+1)))
        s=(s * calc_pattern(A[m+1]-1 - (A[m]+1)))%1000000007
print(int(s))




### FIXED CODE ###

N,M=map(int,input().split())
A=[int(input()) for n in range(M)]
S=[1]*(N+1)
for a in A:
  S[a]=0
for i in range(2,N+1):
  S[i]=(S[i-1]+S[i-2])%1000000007*S[i]

print(S[-1])
N, M = map(int, input().split())
Alist = [[]]*M
for i in range(M):
  Alist[i] = list(map(str, input().split()))
collect = [False]*N
NP = 0
NAC = 0
results = [False]*N
for k in range(M):
  if Alist[k][1] == 'AC':
    results[int(Alist[k][0])] = True

for j in range(M):
  if Alist[j][1] == 'WA' and results[int(Alist[j][0])] == True:
    NP += 1
  elif collect[int(Alist[j][0])-1] == False and Alist[j][1] == 'AC':
    NAC += 1
    collect[int(Alist[j][0])-1] = True
print(NAC, " ", NP)

### FIXED CODE ###

N, M = map(int, input().split())
Alist = [[]]*M
for i in range(M):
  Alist[i] = list(map(str, input().split()))
collect = [False]*N
NP = 0
NAC = 0
results = [False]*N
for k in range(M):
  if Alist[k][1] == 'AC':
    results[int(Alist[k][0])-1] = True

for j in range(M):
  if Alist[j][1] == 'WA' and results[int(Alist[j][0])-1] == True and collect[int(Alist[j][0])-1] == False:
    NP += 1
  elif collect[int(Alist[j][0])-1] == False and Alist[j][1] == 'AC':
    NAC += 1
    collect[int(Alist[j][0])-1] = True
print(NAC, " ", NP)
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**6 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
f = 1
finv = 1
p2 = 1
for i in range(1, MAX_N+1):
    # fac[i] = fac[i-1] * i % MOD
    f *= i
    f %= MOD
    fac[i] = f
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    # fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD
    finv *= pow(i, MOD-2, MOD)
    finv %= MOD
    fac_inv[i] = finv
    p2 *= 2
    p2 %= MOD
    mod_pow2_n[i] = p2

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
def single_mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    if r > n - r:
        r = n - r
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
    return ret

n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)
N, A, B = map(int, input().split())
def solve():
    if A + B - 1 <= N and N <= A * B:
        s = []
        q = (N - B) // (A - 1)
        r = (N - B) % (A - 1)
        if r == 0:
            q -= 1
            r = A - 1
        for i in range(B - q - 1):
            s.append(N - i)
        for i in range(r + 1):
            s.append(A * q + 1 + i)
        for i in range(q - 1, -1, -1):
            for j in range(A):
                s.append(A * i + j + 1)
        return " ".join(map(str, s))
    else:
        return "-1"
print(solve())

### FIXED CODE ###

N, A, B = map(int, input().split())
def solve():
    if A + B - 1 <= N and N <= A * B:
        if A == 1:
            return [i for i in range(N, 0, -1)]
        s = []
        q = (N - B) // (A - 1)
        r = (N - B) % (A - 1)
        if r == 0:
            q -= 1
            r = A - 1
        for i in range(B - q - 1):
            s.append(N - i)
        for i in range(r + 1):
            s.append(A * q + 1 + i)
        for i in range(q - 1, -1, -1):
            for j in range(A):
                s.append(A * i + j + 1)
        return s
    else:
        return [-1]
print(" ".join(map(str, solve())))
N = int(input())
ans = set()
for i in range(N):
    tmp = set()
    x, y, h = map(int, input().split())
    for cx in range(0,101):
        for cy in range(0, 101):
            ch = abs(x-cx) + abs(y-cy) + h
            if ch < 1:
                continue
            tmp.add((cx, cy, ch))
    if ans == set():
        ans = tmp
        continue
    elif tmp == set():
        continue
    ans = ans & tmp
ans = list(ans)[0]
print(ans[0], ans[1], ans[2])


### FIXED CODE ###

N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
ansx = 0
ansy = 0
ansh = 0
for x in range(101):
  for y in range(101):
    hset = set()
    for i in range(N):
      xyhi = xyh[i]
      if xyhi[2] == 0:
        continue
      hset.add(abs(xyhi[0]-x) + abs(xyhi[1]-y) + xyhi[2])

    if len(hset) == 1 and list(hset)[0] != 0:
      flag = True
      for i in range(N):
        xyhi = xyh[i]
        if xyhi[2] != 0:
          continue
        elif xyhi[2] == 0 and max(list(hset)[0] - abs(xyhi[0]-x) - abs(xyhi[1]-y), 0) == 0:
          continue
        flag = False
        break
      if flag:
        ansx = x
        ansy = y
        ansh = list(hset)[0]

print(ansx, ansy, ansh)
S = input()
T = input()

ans = len(T)

for i in range(len(S) - len(T) + 1):
    diff = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            diff += 1
        l_diff.append(diff)
    ans = min(ans, diff)
    
print(ans)

### FIXED CODE ###

S = input()
T = input()

ans = len(T)

for i in range(len(S) - len(T) + 1):
    diff = 0
    for j in range(len(T)):
        if S[i+j] != T[j]:
            diff += 1
    ans = min(ans, diff)
    
print(ans)
a=input()
text=int(a)
if text>=30
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a=input()
text=int(a)
if text>=30 :
    print('Yes')
else:
    print('No')
def main():
    A, B = input().split()
    print((A - 1) * (B - 1))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    A, B = map(int, input().split())
    print((A - 1) * (B - 1))

if __name__ == "__main__":
    main()
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# B以下で割り切れる
UB_C = B // C
UB_D = B // D
UB_CD = B // lcm(C, D)

UB = B - (UB_C + UB_D - UB_CD)

# A以下で割り切れる
UA_C = A // C
UA_D = A // D
UA_CD = A // lcm(C, D)

UA = A - (UA_C + UA_D - UA_CD)

ans = UB - UA

if A % C != 0 and A % D != 0:
    ans += 1

print(ans)


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


A, B, C, D = map(int, input().split())

# B以下で割り切れる
UB_C = B // C
UB_D = B // D
UB_CD = B // lcm(C, D)

UB = B - (UB_C + UB_D - UB_CD)

# A以下で割り切れる
UA_C = A // C
UA_D = A // D
UA_CD = A // lcm(C, D)

UA = A - (UA_C + UA_D - UA_CD)

ans = UB - UA

if A % C != 0 and A % D != 0:
    ans += 1

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+1)]
DP[0][0] = 0

for i in range(1, N+1):
    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)


### FIXED CODE ###

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)