Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline


r, c, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(k)]
INF = 10 ** 18

item = [[0] * c for i in range(r)]
for i, j, v in info:
    i -= 1
    j -= 1
    item[i][j] = v

OFFSET = (r + 1)
dp = [[-INF] * 4 for i in range((c + 1) * (r + 1))]
for i in range(r + 1):
    dp[i][0] = 0
for j in range(c + 1):
    dp[OFFSET * j][0] = 0
    
for i in range(r):
    for j in range(c):
        val = item[i][j]
        tmp11 = i + 1 + OFFSET * (j + 1)
        tmp = i + 1 + OFFSET * j
        tmp01 = i + OFFSET * (j + 1)

        dp[tmp11][0] = max(dp[tmp][0], dp[tmp01][0], dp[tmp01][1], dp[tmp01][2], dp[tmp01][3])
        dp[tmp11][1] = max(dp[tmp][1], dp[tmp][0] + val,  dp[tmp01][0] + val, dp[tmp01][1] + val, dp[tmp01][2] + val, dp[tmp01][3] + val)
        dp[tmp11][2] = max(dp[tmp][2], dp[tmp][1] + val)
        dp[tmp11][3] = max(dp[tmp][3], dp[tmp][2] + val)
          
print(max(dp[-1]))
                                   

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


r, c, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(k)]
INF = 10 ** 18

item = [[0] * c for i in range(r)]
for i, j, v in info:
    i -= 1
    j -= 1
    item[i][j] = v

OFFSET = (r + 1)
dp = [[-INF] * ((c + 1) * (r + 1)) for i in range(4)]
for i in range(r + 1):
    dp[0][i] = 0
for j in range(c + 1):
    dp[0][OFFSET * j] = 0
    
for i in range(r):
    for j in range(c):
        val = item[i][j]
        tmp11 = i + 1 + OFFSET * (j + 1)
        tmp = i + 1 + OFFSET * j
        tmp01 = i + OFFSET * (j + 1)

        dp[0][tmp11] = max(dp[0][tmp], dp[0][tmp01], dp[1][tmp01], dp[2][tmp01], dp[3][tmp01])
        dp[1][tmp11] = max(dp[1][tmp], dp[0][tmp] + val,  dp[0][tmp01] + val, dp[1][tmp01] + val, dp[2][tmp01] + val, dp[3][tmp01] + val)
        dp[2][tmp11] = max(dp[2][tmp], dp[1][tmp] + val)
        dp[3][tmp11] = max(dp[3][tmp], dp[2][tmp] + val)


print(max(dp[0][(c + 1) * (r + 1) - 1], dp[1][(c + 1) * (r + 1) - 1], dp[2][(c + 1) * (r + 1) - 1], dp[3][(c + 1) * (r + 1) - 1]))
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[0]
for i in range(N-1):
  b=b^a[i+1]
ans=""
for i in range(N):
  if(i<N-1):
    ans+=str(b^a[i])+" "
  else:
    ans+=str(b^a[i])
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[0]
for i in range(N-1):
  b=b^a[i+1]
x=[0 for i in range(N)]
for i in range(N):
  x[i]=b^a[i]
x=map(str,x)
ans=' '.join(x)
print(ans)
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [(A[i], i) for i in range(N)]
    B.sort(reverse = True)

    DP = [[-1 for j in range(N + 1)] for _ in range(N)] #i番目の幼児まで見た時、左からi番目まで埋まっている時の最大値
    DP[0][0] = B[0][0] * abs(B[0][1] - (N - 1))
    DP[0][1] = B[0][0] * B[0][1]

    for i in range(1, N):
        for j in range(i + 1):
            #右に詰める時はjの値は変わらない
            #左に詰めるときはj += 1
            DP[i][j] = max(DP[i][j], DP[i-1][j] + B[i][0] * abs(B[i][1] - (N - 1 - i + j)))
            DP[i][j+1] = max(DP[i][j+1], DP[i-1][j] + B[i][0] * abs(B[i][1] - j))
    print(max(DP[N-1]))

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [(A[i], i) for i in range(N)]
    B.sort(reverse = True)

    DP = [[-1 for j in range(N + 1)] for _ in range(N)] #i番目の幼児まで見た時、左からi番目まで埋まっている時の最大値
    DP[0][0] = B[0][0] * abs(B[0][1] - (N - 1))
    DP[0][1] = B[0][0] * B[0][1]

    for i in range(1, N):
        for j in range(i + 1):
            #右に詰める時はjの値は変わらない
            #左に詰めるときはj += 1
            DP[i][j] = max(DP[i][j], DP[i-1][j] + B[i][0] * abs(B[i][1] - (N - 1 - i + j)))
            DP[i][j+1] = max(DP[i][j+1], DP[i-1][j] + B[i][0] * abs(B[i][1] - j))
    print(max(DP[N-1]))

    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N=int(input())
AS = list(map(int,input().split()))
zero=False
sum = 1
la=len(AS)
for i in range(la):
  A=AS[i]
  if A==0:
    zero=True
    break
  sum = sum * A
if zero==True:
  print(0)
else:
  if sum > 10**18:
    print(-1)
  else:
    print(sum)

### FIXED CODE ###

N=int(input())
AS = list(map(int,input().split()))
if 0 in AS:
  print(0)
  exit()
s = 0
sum = 1
l=len(AS)
for i in range(l):
  A=AS[i]
  sum = sum * A
  if sum > 10**18:
    s=2
    break
if sum > 10**18:
  print(-1)
else:
  print(sum)
### BUGGY CODE ###

from math import factorial
import bisect

def main():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    n = A[-1]
    maxc = 0
    fn = factorial(n)
    i = bisect.bisect_left(A, n // 2)
    for r in [A[i-1], A[i]]:
        comb = (fn // factorial(n - r)) // factorial(r)
        if maxc < comb:
            ans = r
            maxc = comb
    print(n, ans)

main()


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    n = A[-1]
    i = bisect.bisect_left(A, n / 2)
    if n / 2 - A[i-1] <= A[i] - n / 2:
        r = A[i-1]
    else:
        r = A[i]
    print(n, r)

main()
### BUGGY CODE ###

A,B,K = map(int, input().split())

takahashi_cookie = A
aoki_cookie = B
iteration = K

for i in range(0, K):
    if(1 <= takahashi_cookie):
        takahashi_cookie -= 1

    elif(1 <= aoki_cookie):
        aoki_cookie -= 1

    else:
        pass

print(str(takahashi_cookie) + ' ' + str(aoki_cookie))


### FIXED CODE ###

A,B,K = map(int, input().split())

takahashi_cookie = A
aoki_cookie = B
iteration = K

if 0 <= takahashi_cookie - iteration:
  takahashi_cookie -= iteration
 
elif 0 <= aoki_cookie + takahashi_cookie - iteration:
  aoki_cookie = aoki_cookie + takahashi_cookie - iteration
  takahashi_cookie = 0

else:
  takahashi_cookie = 0
  aoki_cookie = 0

print(str(takahashi_cookie) + ' ' + str(aoki_cookie))
### BUGGY CODE ###

from collections import Counter
s = input()
n = len(s)
dp = [0]
mod = 2019
a = 0
for i in range(n):
    a += int(s[n-i-1]) * 10 ** i
    dp.append(a%mod)
ans = 0
c = Counter(dp)
for value in c.values():
    ans += value * (value-1) / 2
print(int(ans))

### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
dp = [0]
mod = 2019
a = 0
for i in range(n):
    a = a + int(s[n-i-1]) * pow(10, i, mod)
    a %= mod
    dp.append(a%mod)
ans = 0
c = Counter(dp)
for value in c.values():
    ans += value * (value-1) / 2
print(int(ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
    ans=0
else:
    for i in range(n):
        ans =ans*a[i]
    if ans > 10**18:
        ans=-1
           
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>10**18:
            s=-1
            break
    print(s)
### BUGGY CODE ###

N = int(input())
#n = range(N)
a = list(int(i) for i in input().split()) #A_i =: a_{i-2}

for i in range(1,N+1):
    print(a.count(i))

### FIXED CODE ###

from collections import Counter

N = int(input())
#n = range(N)
a = list(int(i) for i in input().split()) #A_i =: a_{i-2}

b = Counter(a)
for i in range(1,N+1):
    print(b[i])
### BUGGY CODE ###

from collections import Counter

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

S = Counter(listA)

##key##
key = S.keys()

##dict##
my_dict = {}  

for i in key:
  out = 0
  for a in key:
    if a == i:
      num = S[a]-1
      add = (S[a]-1) * (S[a]-2) /2
      out = out + add      
    else:
      num = S[a]
      add = S[a] * (S[a]-1) /2
      out = out +add
  my_dict[i] = int(out) 

for i in listA:
  print(my_dict[i])


### FIXED CODE ###

from collections import Counter

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

S = Counter(listA)

##key##
key = S.keys()
out = 0
for i in key:
  out = out + S[i] * (S[i]-1) /2

for i in listA:
  test = out - S[i] * (S[i]-1) /2 + (S[i] -1) * (S[i]-2) /2
  print(int(test))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import bisect

N=int(input())
l=list(map(int,input().split()))
l.sort()

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        insert_index = bisect.bisect_left(l[j+1:N],l[i]+l[j])
        ans+=(insert_index)
            
print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import bisect

N=int(input())
l=list(map(int,input().split()))
l.sort()

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        insert_index = bisect.bisect_left(l,l[i]+l[j])
        ans+=(insert_index-j-1)
        
print(ans)
### BUGGY CODE ###

import math
import collections

k = int(input())
gcd_table = [[0] * k for i in range(k)]
for i in range(1, k+1):
    for j in range(i, k+1):
        gcd_table[i-1][j-1] = math.gcd(i, j)

ans = 0
combination_list = [0, 1, 3, 6]
for p in range(1, k+1):
    for q in range(p, k+1):
        if gcd_table[p-1][q-1] == 0:
            tmp_gcd = math.gcd(p, q)
            gcd_table[p-1][q-1] = tmp_gcd
        else:
            tmp_gcd = gcd_table[p-1][q-1]
        for r in range(q, k+1):
            if gcd_table[q-1][r-1] == 0:
                tmp_gcd_2 = math.gcd(q, r)
                gcd_table[q-1][r-1] = tmp_gcd_2
            else:
                tmp_gcd_2 = gcd_table[q-1][r-1]
            unique_num = len(collections.Counter([p, q, r]))
            ans += math.gcd(tmp_gcd, tmp_gcd_2) * combination_list[unique_num]
print(ans)

### FIXED CODE ###

import math
import collections

k = int(input())
gcd_table = [[0] * k for i in range(k)]
for i in range(1, k+1):
    for j in range(i, k+1):
        gcd_table[i-1][j-1] = math.gcd(i, j)

ans = 0
combination_list = [0, 1, 3, 6]
for p in range(1, k+1):
    for q in range(p, k+1):
        if gcd_table[p-1][q-1] == 0:
            tmp_gcd = math.gcd(p, q)
            gcd_table[p-1][q-1] = tmp_gcd
        else:
            tmp_gcd = gcd_table[p-1][q-1]
        for r in range(q, k+1):
            if gcd_table[q-1][r-1] == 0:
                tmp_gcd_2 = math.gcd(q, r)
                gcd_table[q-1][r-1] = tmp_gcd_2
            else:
                tmp_gcd_2 = gcd_table[q-1][r-1]
            unique_num = len(collections.Counter([p, q, r]))
            ans += math.gcd(tmp_gcd, tmp_gcd_2) * combination_list[unique_num]
print(ans)
### BUGGY CODE ###

def main():
    import bisect
    import math
    import sys

    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    for i in range(m):
        tmp=a[n-1]//2
        a.insert(bisect.bisect_left(a,tmp),tmp)
        a.pop(n)
    print(sum(a))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    import math
    import sys
    import heapq
    def f(s):
        return -int(s)

    n,m=map(int,input().split())
    a=list(map(f,input().split()))
    heapq.heapify(a)

    for i in range(m):
        tmp=heapq.heappop(a)
        tmp=math.ceil(tmp/2)
        heapq.heappush(a,tmp)

    print(-sum(a))
    

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = list(input())

delKeta = N-3
Vall = []
ans=[]
for V3 in range(10):
    for V2 in range(10):
        for V1 in range(10):
            Vall.append([V1, V2, V3])

for V in Vall:
    tmp = ''
    i = 0
    j = 0
    while i < N:
        if(V[j] == int(S[i])):
            tmp+=S[i]
            j += 1
        if(j==3):
            ans.append(tmp)
            break
        i+=1

print(len(set(ans)))

### FIXED CODE ###

N = int(input())
S = list(map(int,input()))
count = 0

for x100 in range(10):
    if x100 in S[:N-2]:
        ind_100 = S.index(x100)
        
        for x10 in range(10):
            if x10 in S[ind_100+1:N-1]:
                ind_10 = S[ind_100+1:N-1].index(x10) + ind_100 + 1
                
                for x1 in range(10):
                    if x1 in S[ind_10 + 1:]:
                        count += 1
print(count)
### BUGGY CODE ###

n = int(input())
ans =sum(range(1, n))
print(ans)

### FIXED CODE ###

n = int(input())
ans = n*(n-1)//2
print(ans)
### BUGGY CODE ###

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

A = A + [0]
K = min(K, 100)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)

### FIXED CODE ###

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

A = A + [0]
K = min(K, 50)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)
### BUGGY CODE ###

n, p = map(int,input().split())
s = input()
ans = 0

for i in range(n):
  for j in range(i,n):
    if int(s[i:j+1])%p == 0: ans +=1
print(ans)

### FIXED CODE ###

n,p=map(int,input().split())
if p==2 or p==5:
  print(sum(i+1 for i,x in enumerate(input()) if int(x)%p==0))
  exit()
t=1
y=0
c=[0]*p
for x in map(int,input()[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p
print(sum(i*(i-1)//2 for i in c)+c[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = [int(x) if x != "?" else -1 for x in input().strip()]
n = len(s)
m = 10**9+7
dp = [0] * 26
mul = 1

if s[-1] == -1:
    for i in range(10):
        dp[i] = 1
else:
    dp[s[-1]] = 1

for i in range(2, n + 1):
    mul *= 10

    if s[-i] == -1:
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    dp[a + 13] += dp[k]%m
    else:
        rem = (s[-i] * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                dp[a + 13] += dp[k]%m
    dp[:13] = dp[13:26]
    dp[13:26] = [0]*13
print(dp[5]%m)

### FIXED CODE ###

def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)

dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
V = sum(v)

dp = [[float('inf')] * (V+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で価値がj以上になるように選んだときの重さの最小値
dp[0][0] = 0
for i in range(N):
  for j in range(V+1):
    if v[i] <= j:# 荷物v[i]の価値がjに足りてないのでi番目の荷物を入れる可能性がある
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V + 1):
  if dp[N][j] <= W:
    ans = j    
      
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if (i*R + j*G) == N:
            ans += 1
        if (i*R + j*G) < N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
 
ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G > N:
            break
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

# import math
# import numpy as np

# S = input()
# N = int(input())
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# B = [int(input()) for _ in range(n)]
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

# 二次元配列
# [[inf, inf, inf], [inf, inf, inf]]
# dp = [[float('inf')] * (H + 1) for i in range(N + 1)]

INF = 10 ** 18
dp = [INF] * (20201)
dp[0] = 0

def solve():
    for i in range(H):
        for j in range(N):
            if dp[i] == INF:
                continue
            dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j])
    return min(dp[H:])

print(solve())


### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())
### BUGGY CODE ###

import itertools


N, M = map(int, input().split())
lst = [list(map(int, input().rstrip().split())) for n in range(N)]
maximum = -float("inf")
for pickup in itertools.combinations(lst, M):
    m = abs(sum([pickup[n][0] for n in range(M)])) + abs(sum([pickup[n][1] for n in range(M)])) + abs(sum([pickup[n][2] for n in range(M)]))
    maximum = max(maximum, m)

print(maximum)


### FIXED CODE ###

N, M = map(int, input().split())
lst = [list(map(int, input().rstrip().split())) for n in range(N)]
maximum = -float("inf")
for i in [-1, 1]:
    for j in [-1, 1]:
        for k in [-1, 1]:
            sum_lst = []
            for n in range(N):
                num = lst[n][0] * i + lst[n][1] * j + lst[n][2] * k
                sum_lst.append(num)
            maximum = max(abs(sum(sorted(sum_lst)[:M])), maximum)
            
print(maximum)
### BUGGY CODE ###

def main():
    N, K, *A = map(int, open(0).read().split())
    log_k = 0
    k = K
    while k > 0:
        k >>= 1
        log_k += 1
    # print(log_k)
    work = [[0]*N for i in range(log_k)]
    # level 1
    for i in range(N):
        work[0][i] = A[i]
    for k in range(log_k - 1):
        for i in range(N):
            work[k + 1][i] = work[k][work[k][i] - 1]
    ans = 1
    k = K
    level = 0
    # print(work)
    while k > 0:
        if k & 1 == 1:
            ans = work[level][ans - 1]
        level += 1
        k >>= 1
    print(ans)

def main1():
    N, K, *A = map(int, open(0).read().split())
    visited = [-1]*N
    pos = A[0]
    visited[0] = 0
    visited[pos - 1] = 1
    step = 2
    order = 0
    start = 0
    step_to_start = 0
    while True:
        pos = A[pos - 1]
        if visited[pos - 1] == -1:
            visited[pos - 1] = step
        else:
            step_to_start = visited[pos - 1]
            order = step - step_to_start
            start = pos
            break
        step += 1
    # print(start, step_to_start, order)

    if K <= step_to_start:
        ans = 1
        for i in range(K):
            ans = A[ans - 1]
        print(ans)
        return
    remain = (K - step_to_start) % order
    ans = start
    for i in range(remain):
        ans = A[ans - 1]
    print(ans)

if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
    N, K, *A = map(int, open(0).read().split())
    visited = [-1]*N
    pos = A[0]
    visited[0] = 0
    visited[pos - 1] = 1
    step = 2
    order = 0
    start = 0
    step_to_start = 0
    while True:
        pos = A[pos - 1]
        if visited[pos - 1] == -1:
            visited[pos - 1] = step
        else:
            step_to_start = visited[pos - 1]
            order = step - step_to_start
            start = pos
            break
        step += 1
    # print(start, step_to_start, order)

    if K <= step_to_start:
        ans = 1
        for i in range(K):
            ans = A[ans - 1]
        print(ans)
        return
    remain = (K - step_to_start) % order
    ans = start
    for i in range(remain):
        ans = A[ans - 1]
    print(ans)

if __name__ == '__main__':
  main()
### BUGGY CODE ###

from collections import deque

k = int(input())
limit = 10#最大桁数

start = [i for i in range(1, 10)]#最初にスタートする数
ans = []
q=deque(start)
while q:
	num=q.popleft()
	if len(str(num))>11:#処理終了
		continue#次のQへ
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		q.append(int(str(num)+i))

ans = sorted(ans)
print(ans[k - 1])#k番目の答えを創出

### FIXED CODE ###

from collections import deque

k = int(input())
limit = 10#最大桁数

start = [i for i in range(1, 10)]#最初にスタートする数
ans = []
def DFS(num):
	if len(str(num))>11:#処理終了
		return 1
	ans.append(num)
	last=str(num)[-1]
	if last == "0":
		add = ['0', '1']
	elif last == '9':
		add = ['8',"9"] 
	else:
		add = [str(int(last) - 1), str(int(last)), str(int(last) + 1)]
	for i in add:
		DFS(int(str(num)+i))

for j in start:
	DFS(j)

ans = sorted(ans)
print(ans[k - 1])#k番目の答えを創出
### BUGGY CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[int(s[i:])%p for i in range(n)]+[0]
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

### FIXED CODE ###

#E
from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    #print(U)
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)
### BUGGY CODE ###

R,G,B,N =map(int,input().split())

cnt =0
    
for r in range(N+1):
    
    for g in range(N+1):
        
        ball =  r*R+g*G  
        
        res = N-ball
        
        if  res >=0  and res%B ==0:
            cnt+=1
    
print(cnt)
            


### FIXED CODE ###

R,G,B,N =map(int,input().split())

cnt =0
    
for r in range(int(N/R)+1):
  ball = N-r*R 
  for g in range(int(ball/G)+1):
    res = N- (r*R+g*G)
    if  res >=0 and res%B ==0:
      cnt+=1
    
print(cnt)
### BUGGY CODE ###

N,S,*A = map(int, open(0).read().split())
dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1
appeared = set([0])
for i in range(1,N+1):
    temp = A[i-1]
    ts = set()
    for x in appeared:
        dp[i][x] += (dp[i-1][x]*2) % 998244353
        if temp + x <= S:
            dp[i][temp+x] += dp[i-1][x]
            if temp + x not in appeared:
                ts.add(temp+x)
    appeared |= ts
print(dp[N][S]%998244353)

### FIXED CODE ###

N,S,*A = map(int, open(0).read().split())
dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1
appeared = set([0])
for i in range(1,N+1):
    temp = A[i-1]
    ts = set()
    for x in appeared:
        dp[i][x] += (dp[i-1][x]*2) % 998244353
        if temp + x <= S:
            dp[i][temp+x] += dp[i-1][x]
            if temp + x not in appeared:
                ts.add(temp+x)
    appeared |= ts
print(dp[N][S]%998244353)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for k in range(N):
    buf = A[k]
    ans = 0
    A[k] = 0
    for l in range (N-1):
        ans = ans + (A.count(l+1))*(A.count(l+1)-1)/2
    print(int(ans))
    A[k] = buf


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 0
c = collections.Counter(A)
for l in c.values():
    ans = ans + l*(l-1)/2
for k in A:
    print(int(ans-(c[k]-1)))
### BUGGY CODE ###

N = int(input())
V = [int(x.strip()) for x in input().split()]
C = [int(x.strip()) for x in input().split()]

Z = [0 for i in range(2**N)]

for i in range(1, 2**N):
    select = []
    temp = i
    for n in reversed(range(1, N+1)):
        if temp - 2**(n-1) >= 0:
            temp = temp - 2**(n-1)
            select.append(n-1)
    Z[i] = sum([V[j] for j in select]) - sum([C[j] for j in select])
print(max(Z))

### FIXED CODE ###

N = int(input())
V = [int(x.strip()) for x in input().split()]
C = [int(x.strip()) for x in input().split()]

Z = [V[i] - C[i] for i in range(N)]
print(sum([z for z in Z if z > 0]))