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

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

dp = [[[0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k == 0: continue
            dp[i][j][k] += N
            if i>0: dp[i][j][k] += i*dp[i-1][j][k]
            if j>0: dp[i][j][k] += j*dp[i+1][j-1][k]
            if k>0: dp[i][j][k] += k*dp[i][j+1][k-1]
            dp[i][j][k]/=(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])




### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

dp = [[[0.0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]
            if j>0: tmp += j*dp[i+1][j-1][k]
            if k>0: tmp += k*dp[i][j+1][k-1]
            dp[i][j][k] = tmp/(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
inf_ = float("inf")
grid = [[inf_] * W for _ in range(H)]
stack = []
dire = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            stack.append([i,j,0])
while stack:
    i, j, now = stack.pop()
    grid[i][j] = now
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] > now+1:
            stack.append([ny,nx,now+1])
for g in grid:
    ans = max(ans,max(g))
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for _ in range(H)]
q = deque([])
grid = [[-1] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = grid[i][j]
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] < 0:
            q.append((ny, nx))
            grid[ny][nx] = grid[i][j] + 1
 
print(d)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    n=int(input())
    S=list(input())
    q=int(input())
    set_s={chr(ord('a')+i):[] for i in range(26)}
    for i,s in enumerate(S):
        set_s[s].append(i)
    for _ in range(q):
        query=input().split()
        if query[0]=="1":
            i,c=int(query[1])-1,query[2]
            if S[i]==c:continue
            set_s[S[i]].remove(i)
            set_s[c].insert(bisect_left(set_s[c],i),i)
            S[i]=c
        else:
            l,r=int(query[1])-1,int(query[2])-1
            ans=0
            for i in range(26):
                ss=chr(ord('a')+i)
                if bisect(set_s[ss],r)>bisect_left(set_s[ss],l):
                    ans+=1
            print(ans)


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    n=int(input())
    S=list(input())
    q=int(input())
    set_s={chr(ord('a')+i):[] for i in range(26)}
    for i,s in enumerate(S):
        set_s[s].append(i)
    for _ in range(q):
        query=input().split()
        if query[0]=="1":
            i,c=int(query[1])-1,query[2]
            if S[i]==c:continue
            set_s[S[i]].remove(i)
            set_s[c].insert(bisect_left(set_s[c],i),i)
            S[i]=c
        else:
            l,r=int(query[1])-1,int(query[2])-1
            ans=0
            for i in range(26):
                ss=chr(ord('a')+i)
                if bisect(set_s[ss],r)>bisect_left(set_s[ss],l):
                    ans+=1
            print(ans)


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

s = input()
q = int(input())

j = ''.join
turn = 0
for _ in range(q):
    query = input()
    if len(query) == 1:
        turn += 1
    else:
        two, f, c = query.split()
        if f == '1':
            if turn % 2 == 0:
                s = j([c, s])
            else:
                s = j([s, c])
        else:
            if turn % 2 == 0:
                s = j([s, c])
            else:
                s = j([c, s])

if turn % 2 == 0:
    print(s)
else:
     print(s[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().strip()
q = int(input())
query = [list(input().strip().split()) for _ in range(q)]

left = ''
right = ''
t = False
for ls in query:
    if len(ls) == 1:
        t = not t
    else:
        two, f, c = ls
        if f == '1':
            if t:
                right += c
            else:
                left += c
        else:
            if t:
                left += c
            else:
                right += c

if t:
    print(right[::-1] + s[::-1] + left)
else:
    print(left[::-1] + s + right)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=np.count_nonzero(now)
    ans+= ((pow(2,59-i,mod)* (q*(q-1))%mod)%mod *pow(2,-1,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)
    
     


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [((A[i]>>(59-j))) & 1 for j in range(60)]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


print((ans)%mod)
### BUGGY CODE ###

import queue
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b)
    graph[b-1].append(a)
ans = [0]* n
flag = [0]*n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    flag[tmp-1] = 1
    for i in graph[tmp-1]:
        if flag[i-1] == 0:
            q.append(i)
            if ans[i-1] == 0:
                ans[i-1] = tmp
if sum(flag) == n:
    print('Yes')
    for i in range(1,n):
        print(ans[i])
        
else:
    print('No')

### FIXED CODE ###

import queue
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b)
    graph[b-1].append(a)
ans = [0]* n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    for i in graph[tmp-1]:
        if ans[i-1] == 0:
            q.append(i)
            ans[i-1] = tmp
                
if 0 in ans:
    print('No')
        
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
if __name__ == '__main__':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)
                
                

### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    for s in range(A[0] * 2, -1, -2):
        mt = [None] * N
        mt[0] = s
        for n in range(N-1):
            if mt[n] > A[n+1] * 2:
                break
            mt[n+1] = (A[n+1] - mt[n]//2) * 2

        if mt[N-1] != None:
            if mt[N-1] //2 + mt[0] // 2 == A[0]:
                print(mt[-1], ' '.join(list(map(str, mt[:-1]))))
                return

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [None] * len(A)
    X[0] = sum(A) - 2 * sum([A[i] for i in range(1, len(A), 2)])
    for i in range(len(A)-1):
        X[i+1] = 2 * A[i] - X[i]
    
    print(' '.join(list(map(str, X))))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = sorted(list(map(int, input().split())))

D_list = []
for _ in range(M):
    B_i, C_i = map(int, input().split())
    D_list += [C_i] * B_i

D_list = sorted(D_list, reverse=True)

# Operate Top min(len(D_list), N) of BC_sorted
len_target = min(len(D_list), N)
for i in range(len_target):
    if A_list[i] < D_list[i]:
        A_list[i] = D_list[i]
    else:
        break

# Output sumed A_list
print(sum(A_list))

### FIXED CODE ###

N, M = map(int, input().split())
A_list = sorted(list(map(int, input().split())))

BC_list = [tuple(map(int, input().split())) for _ in range(M)]
BC_list.sort(key=lambda x: x[1], reverse=True)

n_replace = 0
sum_target = 0
is_broken = False
for B, C in BC_list:
    if n_replace + B <= N:
        for A in A_list[n_replace:n_replace+B]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                is_broken = True
                break
    else:
        remaining = N - n_replace
        for A in A_list[n_replace:n_replace+remaining]:
            if A < C:
                sum_target += C
                n_replace += 1
            else:
                is_broken = True
                break
    if is_broken is True:
        break
if n_replace < N:
    sum_target += sum(A_list[n_replace:])

# Output sumed A_list
print(sum_target)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))  
      


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
### BUGGY CODE ###

def main():
    A, B, N = (int(x) for x in input().split())
    mini = 0
    if N >= B:
        for x in range(B-1, N+1, B):
            k = x / B
            ans = int(A*k) - int(k)
            if ans > mini:
                mini = ans
    else:
        ans = int(A*(N)/B)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    A, B, N = (int(x) for x in input().split())
    mini = 0
    if N >= B:
        ans = int(A*(B-1)/B)
    else:
        ans = int(A*(N)/B)
    print(ans)


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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i:0 for i in range(n + 1) if is_prime[i]}

n = int(input())
a = list(map(int,input().split()))
d = primes(max(a))

for i in range(n):
    for k in d.keys():
        flag = False
        while True:
            if a[i] % k == 0:
                a[i] //= k
                flag = True
            else:
                break
        if flag:
            d[k] += 1
        if a[i] == 1:
            break
flag = True
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v > 1:
        flag = False

if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")

### FIXED CODE ###

def primes(n):
    is_prime = [-1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 1
    for i in range(2, n + 1):
        if is_prime[i] != -1:
            continue
        for j in range(i, n + 1, i):
            if is_prime[j] == -1:
                is_prime[j] = i
    return is_prime

n = int(input())
a = list(map(int,input().split()))
s = primes(max(a))
d = {}
for i in a:
    now = i
    while s[now] != 1:
        t = s[now]
        d[t] = d.get(s[now],0) + 1
        while now % t == 0:
            now //= t
            
                
            
    
flag = True
for v in d.values():
    if v == n:
        print("not coprime")
        exit()
    elif v > 1:
        flag = False

if flag:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


# Priority QueueとしてHeapを使う
# Pythonのheapqは小さい順に取り出すので、-1を掛けて負数としてpushしていく
#   (-Ai-Bj-Ck, i, j, k)
# 取り出したi, j, kについて、(i+1, j, k), (i, j+1, k), (i, j, k+1)に対応するタプルをpushする
# ただし、すでにpushした値は入れないようにする

import heapq

def make(i, j, k):
    return (-A[i]-B[j]-C[k], i, j, k)


used = [[[False] * Z for i in range(Y)] for j in range(X)]
l = []

heapq.heappush(l, make(0, 0, 0))
used[0][0][0] = True

for cnt in range(K):
    V, i, j, k = heapq.heappop(l)
    
    if i < X - 1 and not used[i+1][j][k]:
        heapq.heappush(l, make(i+1, j, k))
        used[i+1][j][k] = True
    
    if j < Y - 1 and not used[i][j+1][k]:
        heapq.heappush(l, make(i, j+1, k))
        used[i][j+1][k] = True
    
    if k < Z - 1 and not used[i][j][k+1]:
        heapq.heappush(l, make(i, j, k+1))
        used[i][j][k+1] = True
    
    print(-V)




### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


# Priority QueueとしてHeapを使う
# Pythonのheapqは小さい順に取り出すので、-1を掛けて負数としてpushしていく
#   (-Ai-Bj-Ck, i, j, k)
# 取り出したi, j, kについて、(i+1, j, k), (i, j+1, k), (i, j, k+1)に対応するタプルをpushする
# ただし、すでにpushした値は入れないようにする

import heapq

def make(i, j, k):
    return (-A[i]-B[j]-C[k], i, j, k)


used = set()
l = []

heapq.heappush(l, make(0, 0, 0))
used.add((0, 0, 0))

for cnt in range(K):
    V, i, j, k = heapq.heappop(l)
    
    if i < X - 1 and (i+1, j, k) not in used:
        heapq.heappush(l, make(i+1, j, k))
        used.add((i+1, j, k))
    
    if j < Y - 1 and (i, j+1, k) not in used:
        heapq.heappush(l, make(i, j+1, k))
        used.add((i, j+1, k))
    
    if k < Z - 1 and (i, j, k+1) not in used:
        heapq.heappush(l, make(i, j, k+1))
        used.add((i, j, k+1))
    
    print(-V)
### BUGGY CODE ###

# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


def main():
    n = II()
    A = LI()
    A.sort()
    A.reverse()

    t = A[0]
    pre = [0] * n
    pre[0] = A[0]
    for i in range(1, n):
        pre[i] = gcd(pre[i - 1], A[i])
    res = pre[-1]
    for i in range(n):
        t = pre[i]
        for j in range(i + 2, n):
            t = gcd(t, A[j])
        res = max(res, t)

    return res


print(main())


### FIXED CODE ###

# coding:utf-8

import sys
import fractions

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


def main():
    n = II()
    A = LI()
    A.sort()
    A.reverse()

    pre = [0] * n
    pre[0] = A[0]
    for i in range(1, n):
        pre[i] = gcd(pre[i - 1], A[i])
    res = pre[-1]
    for i in range(n):
        t = pre[i]
        for j in range(i + 2, n):
            t = gcd(t, A[j])
            if t == pre[j - 1]:
                t = -1
                break
        res = max(res, t)

    t = A[1]
    for a in A[1:]:
        t = gcd(t, a)

    return max(res, t)


print(main())
### BUGGY CODE ###

n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    for a in range(10):
        for b in range(10):
            if a - b == c:
                ret[0][0] = min(ret[0][0], a + b)
            if 10 + a - b == c:
                ret[0][1] = min(ret[0][1], a + b)
            if a - 1 - b == c:
                ret[1][0] = min(ret[1][0], a + b)
            if 10 + a - 1 - b == c:
                ret[1][1] = min(ret[1][1], a + b)
    return ret


dp = [[0 for _ in range(l+1)] for _ in range(2)]

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

print(min(dp[0][l], dp[1][l]+1))
# print(dp)

### FIXED CODE ###

n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    # for a in range(10):
    #     for b in range(10):
    #         if a - b == c:
    #             ret[0][0] = min(ret[0][0], a + b)
    #         if 10 + a - b == c:
    #             ret[0][1] = min(ret[0][1], a + b)
    #         if a - 1 - b == c:
    #             ret[1][0] = min(ret[1][0], a + b)
    #         if 10 + a - 1 - b == c:
    #             ret[1][1] = min(ret[1][1], a + b)
    for b in range(10):
        a = c + b
        if 0 <= a < 10:
            ret[0][0] = min(ret[0][0], a+b)
        a = c + b - 10
        if 0 <= a < 10:
            ret[0][1] = min(ret[0][1], a+b)
        a = c + b + 1
        if 0 <= a < 10:
            ret[1][0] = min(ret[1][0], a + b)
        a = c + b - 10 + 1
        if 0 <= a < 10:
            ret[1][1] = min(ret[1][1], a + b)
    return ret


dp = [[0 for _ in range(l+1)] for _ in range(2)]

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

print(min(dp[0][l], dp[1][l]+1))
# print(dp)
### BUGGY CODE ###

s = input()
K = int (input())


def sort_here(ll):  # バブルソート
    for m in range(len(ll)):
        for n in range(len(ll)-1-m):
            A, B = compare(ll[n], ll[n+1])
            ll[n] = A
            ll[n + 1] = B
    return ll


def compare(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    a = len(A)
    b = len(B)

    if a > b:
        if A[:b] == B:
            return B, A
    elif b > a:
        if B[:a] == A:
            return A, B

    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B


# まずはありうるsubstringを準備
i_list = []
for i in range(1, len(s) + 1):
    # i文字数のsutringをまずは作る
    for j in range(len(s) - i + 1):
        cand = s[j:j+i]
        if cand not in i_list:
            i_list.append(s[j:j+i])

#print(i_list)

# 並び替え
i_list = sort_here(i_list)
#print(i_list)


# 出力
print(i_list[K-1])


### FIXED CODE ###

s = input()
l = len(s)
k = int(input())


def compare(a, b):
    ll = [a, b]
    ll = sorted(ll)
    return ll[0] == a


db = []
for length in range(1, k + 1):
    for start in range(l + 1 - length):
        candidate = s[start:start+length]
        if len(db) >= 5:
            if compare(candidate, db[-1]):
                if candidate not in db:
                    db.append(candidate)
                    db = sorted(db)
                    db = db[:5]
        else:
            if candidate not in db:
                db.append(candidate)
                db = sorted(db)

print(sorted(db)[k-1])
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
count = 0
for i in range(k):
    if a > 0:
        count += 1
        a -= 1
        continue
    elif a == 0 and b > 0:
        b -= 1
        continue
    else:
        count -= 1
        c -= 1
print(count)


### FIXED CODE ###

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

xa = min(a,k)
k1 = k-xa
xb = min(b,k1)
k2 = k1-xb
xc = k2

print(xa-xc)