Harryxun/stf_run huggingface dataset:
N = [0] + list(map(int, input()))
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+2) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(K+1):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

### FIXED CODE ###

n = input()
a = list(n)
k = int(input())
n = len(a)
for i in range(n):
    a[i] = int(a[i])
dp = [[[0 for i in range(2)] for i in range(k+2)]for i  in range(n)]
dp[0][0][0] = 1
dp[0][1][0] = a[0]-1
dp[0][1][1] = 1
for i in range(n-1):
    for j in range(k+1):
        if a[i+1] == 0:
            dp[i+1][j][1] += dp[i][j][1]
            dp[i+1][j][0] += dp[i][j][0]
            dp[i+1][j+1][0] += dp[i][j][0]*9
        else:
            dp[i+1][j][0] += dp[i][j][0]+dp[i][j][1]
            dp[i+1][j+1][0] += dp[i][j][1]*(a[i+1]-1)+dp[i][j][0]*9
            dp[i+1][j+1][1] += dp[i][j][1]
print(dp[n-1][k][0]+dp[n-1][k][1])
import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    safe = list(set(range(10)) - set(D))
    safe = sorted(safe)

    n = [c for c in str(N)]
    for i in range(len(n)):
        if int(n[i]) in safe:
            continue
        
        for s in safe:
            if s > int(n[i]):
                n[i] = str(s)
                replaced = i
                break
        break

    for i in range(replaced+1, len(n)):
        n[i] = str(safe[0])

    return ''.join(n)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, K = map(str, input().split())
    D = list(map(str, input().split()))

    nums = set([str(i) for i in range(10)])
    safe = sorted(list(nums - set(D)))
    min_safe = safe[0]
    if min_safe == '0':
        min_safe = safe[1]

    digit = len(str(N))
    safe_num = list(product(safe, repeat=digit))
    ans = 10**5
    for n in safe_num:
        m = int(''.join(n))
        l = int(min_safe + ''.join(n))
        if m >= int(N):
            ans = min(ans, m)

        if l >= int(N):
            ans = min(ans, l)


    return ans


if __name__ == '__main__':
    print(main())
from collections import Counter
import sys

H,W,M,*hw = map(int,open(0).read().split())

h = hw[::2]
w = hw[1::2]

bomb = [[0]*W for _ in range(H)]
for hi,wi in zip(h,w):
    bomb[hi-1][wi-1] = 1


raw_count = Counter(h)
col_count = Counter(w)

raw_max = raw_count.most_common()[0][1]
col_max = col_count.most_common()[0][1]

ans = 0
for hi, rcount in raw_count.most_common():
    if rcount<raw_max:break
    for wi, ccount in col_count.most_common():
        if ccount<col_max: break
        
        if bomb[hi-1][wi-1]==1:
            ans = raw_max + col_max - 1
        else:
            print(raw_max + col_max)
            sys.exit()

print(ans)


### FIXED CODE ###

from collections import Counter
import sys

H,W,M,*hw = map(int,open(0).read().split())

h = hw[::2]
w = hw[1::2]

hw_set = set((hi,wi) for hi,wi in zip(h,w))


raw_count = Counter(h).most_common()
col_count = Counter(w).most_common()


raw_max = raw_count[0][1]
col_max = col_count[0][1]

ans = 0
for hi, rcount in raw_count:
    if rcount<raw_max:break
    for wi, ccount in col_count:
        if ccount<col_max: break
        
        if (hi,wi) in hw_set:
            ans = raw_max + col_max - 1
        else:
            print(raw_max + col_max)
            sys.exit()

print(ans)
A,B=map(int(input.split()))

if (A+B)%2==1:
  print("IMPOSSIBLE")
  
else:
  print((A+B)/2)

### FIXED CODE ###

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

if (A+B)%2==1:
  print("IMPOSSIBLE")
  
else:
  print((A+B)//2)
n, k = map(int, input().split())
a_lst = list(map(int, input().split()))
a_lst.sort()
if n > k or k == 3:
    print(a_lst[0]+a_lst[1]+a_lst[2])
elif k == 2:
    print(a_lst[0]+a_lst[1])
else:
    print(a_lst[0])

### FIXED CODE ###

n, k = map(int, input().split())
a_lst = list(map(int, input().split()))
a_lst.sort()

ans = 0

for i in range(k):
    ans += a_lst[i]
print(ans)
S = input()
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else:
    print("No")
n=int(input())
chars = "Xabcdefghijklmnopqrstuvwxyz"

n_rem = n
ans = ""

while True:
    x = n_rem%26
    if x == 0:
        x = 26
    ans += chars[x]

    n_rem -= x

    if n_rem == 0:
        break

    n_rem //==26

print(ans[::-1])

### FIXED CODE ###

def alpha2num(alpha):
    num=0
    for index, item in enumerate(list(alpha)):
        num += pow(26,len(alpha)-index-1)*(ord(item)-ord('A')+1)
    return num

def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)

n=int(input())

s = num2alpha(n)
print(s.lower())
import sys
X = input()

if int(X) < 100:
    print(0)
    sys.exit(1)
    
tmp = int(X[-2] + X[-1])

iteration = 0

for i in range(5, 0, -1):
    iteration = tmp // i
    tmp %= i
    
    if tmp == 0:
        break

if (iteration * 100) >= int(X):
    print(1)
else:
    print(0)

### FIXED CODE ###

X = int(input())
c = X // 100

if (c * 100) <= X <= (c * 105):
    print(1)
else:
    print(0)
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    for i in range(H):
        for j in range(W):
            if(s[i][j] == '#'):
                f = False
                for k in range(4):
                    iy = i+dy[k]
                    ix = j+dx[k]
                    if(0 <= iy < H and 0 <= ix < W and s[iyw][ix] == '#'):
                        f = True
                if(not f):
                    print(NO)
                    exit()
                
    print(YES)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):

    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    for i in range(H):
        for j in range(W):
            if(s[i][j] == '#'):
                f = False
                for k in range(4):
                    iy = i+dy[k]
                    ix = j+dx[k]
                    if(0 <= iy < H and 0 <= ix < W and s[iy][ix] == '#'):
                        f = True
                if(f == False):
                    print(NO)
                    exit()
                
    print(YES)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()
n = int(input())
s = input()

for i in range(1,n-1):
    a = set(s[:i])
    b = set(s[i:])
    cnt = len(a) + len(b) - len(s)
    c = max(c,cnt)

print(c)

### FIXED CODE ###

n = int(input())
s = input()
c = 0

for i in range(1,n-1):
    a = set(s[:i])
    b = set(s[i:])
    cnt = len(a) + len(b) - len(a|b)
    c = max(c,cnt)

print(c)
d, g = map(int, input().split())
p = [[0,0] for i in range(d)]
for i in range(d):
    p[i][0], p[i][1] = map(int, input().split())
ans = 0
sum = 0
i = d
j = 0
extra_ans = [p[i][0] * (i+1) * 100 + p[i][1] for i in range(d)]
while sum < g:
    j += 1
    ans += 1
    sum += i * 100
    if j == p[i-1][0]:
        sum += p[i-1][1]
        i -= 1
        j = 0
    if sum + extra_ans[i-2] >= g :
        tmp = ans + p[i-2][0]
if tmp < ans:
    ans = tmp
for i in range(d):
    if p[i][0] * (i+1) * 100 + p[i][1] >= g and p[i][0] < ans:
        ans = p[i][0]
print(ans)


### FIXED CODE ###

# &演算子は、bit形式には使えない。でも、数値には使える
d, g = map(int, input().split())
p = [[0, 0] for i in range(d)]
for i in range(d):
    p[i][0], p[i][1] = map(int, input().split())
## bit全探索

ans = 100000
for i in range(2 ** d):
    sum = 0
    ans_tmp = 0
    s = bin(i)
    #　得点の合計とそれまでの数を反映。
    for j in range(d):
        if bin(2 ** j) == bin(2 ** j & i):
            sum += p[j][0] * (j+1) * 100 + p[j][1]
            ans_tmp += p[j][0]
    if sum < g:
        for j in range(d-1, -1, -1):
            if bin(2 ** j) != bin(2 ** j & i):
                for k in range(p[j][0]-1):
                    sum += (j+1) * 100
                    ans_tmp += 1
                    if g <= sum:
                        break
                if g <= sum:
                    if ans_tmp < ans:
                        ans = ans_tmp
                    break
            else:
                continue
    else:
        if ans_tmp < ans:
            ans = ans_tmp
print(ans)
a, b, c = [int(i) for i in input().split()]

if a > b:
  swap(a, b)

if b > c:
  swap(b, c)

if a > b:
  swap(a, b)

print(a+b)


### FIXED CODE ###

a, b, c = [int(i) for i in input().split()]

if a > b:
  a, b = b, a

if b > c:
  b, c = c, b

if a > b:
  a, b = b, a

print(a+b)
N, W = [int(i) for i in input().split()]
weight, value = [], []

for i in range(N):
    w, v = [int(i) for i in input().split()]
    weight.append(w); value.append(v);

dp = [[0 for _ in range(110)] for _ in range(100100)]

for i in range(N):
    for j in range(W+1):
        if (j-weight[i] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [], []

for i in range(N):
    w, v = [int(i) for i in input().split()]
    weight.append(w); value.append(v);
weight.append(0)
value.append(0)

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if (j-weight[i] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])
a,b,c,d=map(int,input().spit())
p=a*c
q=a*d
r=b*c
s=b*d
print(max(p,q,r,s))


### FIXED CODE ###

a,b,c,d=map(int,input().split())
p=a*c
q=a*d
r=b*c
s=b*d
print(max(p,q,r,s))
h,w = map(int,input().split())
Array = [list(map(int, input().split())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=char(num)
    
for i in Array:
  print(*Array)

### FIXED CODE ###

h,w = map(int,input().split())
Array = [list(map(str,input())) for _ in range(h)]
dx = [1,1,0,-1,-1,-1,0,1]
dy = [0,1,1,1,0,-1,-1,-1]
for i in range(h):
  for j in range(w):
    if Array[i][j]=='#':
      continue
    num=0
    for d in range(8):
      ni = i+dy[d]
      nj = j+dx[d]
      if ni<0 or h<=ni:
        continue
      if nj<0 or w<=nj:
        continue
      if Array[ni][nj]=='#':
        num=num+1
    Array[i][j]=str(num)
    
for i in Array:
  print(*i, sep='')
n=int(input())
a=sorted(list(map(int,input(.split()))))
p=a[n//2-1]
q=a[n//2]
print(q-p)

### FIXED CODE ###

k=int(input())
d=sorted(list(map(int,input().split())))
ans=0
for i in range(d[int(len(d)/2)-1]+1,d[int(len(d)/2)]+1):
    ans+=1
print(ans)
def sol():
    N, Q = map(int, input().split())
    edge = [[] for _ in range(N)]

    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)

    ans = [0 for _ in range(N)]

    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    def calc(now, parent):
        ans[now] += ans[parent]
        for to in edge[now]:
            if to != parent:
                calc(to, now)
        return

    calc(0, -1)
    print(*ans)


sol()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

P = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    P[p - 1] += x

ans = [-1] * N
st = deque([(0, 0)])
while st:
    now, val = st.pop()

    if ans[now] >= 0:
        continue
    val += P[now]
    ans[now] = val

    for to in edges[now]:
        st.append((to, val))

print(*ans)
# atcoder Educational DP contest/DP まとめコンテスト
# B-Frog2

def get_inputs():
    [n, k] = [int(x) for x in input().split()]
    h = list(map(int, input().split()))
    
    return n, k, h


if __name__ == "__main__":
    # 入力を受け取る
    # n 足場の数 2<= N <= 10**5
    # k k本先の足場まで飛ぶことができる 1<=K<=100
    # h 足場の高さ 配列
    n, k, h = get_inputs()
    
    # dp[i]はi番目(0<=i<n)の足場に到達するまでに必要な最小コスト
        
    dp = [10000000000] * (n + 100)        # k個分を含む配列を用意し最大値で初期化する
    dp[0] = 0                             # 0番目の足場はコスト0
    
    # 足場iからj個先まで行く場合の最小コストを求める
    for i in range(0, n - 1):
        for j in range(1, k + 1):
            dp[i + j] = min(dp[i] + abs(h[i + j] - h[i]), dp[i + j])
    
    print(dp[n-1])
      

### FIXED CODE ###

# atcoder Educational DP contest/DP まとめコンテスト
# B-Frog2

def get_inputs():
    [n, k] = [int(x) for x in input().split()]
    h = list(map(int, input().split()))
    
    return n, k, h


if __name__ == "__main__":
    # 入力を受け取る
    # n 足場の数 2<= N <= 10**5
    # k k本先の足場まで飛ぶことができる 1<=K<=100
    # h 足場の高さ 配列
    n, k, h = get_inputs()
    
    ########## first try
    # for文の二重ループではTLEになってしまう
    # dp = [10000000000] * (n + k)        # k個分を含む配列を用意し最大値で初期化する
    # h= h + [100000] * k
    # dp[0] = 0                             # 0番目の足場はコスト0
    # 足場iからj個先まで行く場合の最小コストを求める
    # for i in range(0, n - 1):
    #    for j in range(1, k + 1):
    #        dp[i + j] = min(dp[i] + abs(h[i + j] - h[i]), dp[i + j])
    # print(dp[n-1])
    
    ########## second try
    # 前案より速度は改善したが、まだ一部の問題でTLEになる
    # dp = [10**9] * n
    # dp[0] = 0
    #
    # for i in range(1, n):
    #     mc = 10**9
    #     for j in range(max(0, i - k), i):
    #         mc = min(mc, dp[j] + abs(h[i] - h[j]))
    #    dp[i] = mc
    # print(dp[n-1])
    
    ########## third try
    # 二重ループを内包表記表現に変更
    # zipを使うのがミソ
    
    dp = [10**9] * n
    dp[0] = 0
    for i in range(1, n):
        j = max(0, i - k)
        dp[i] = min([dd + abs(h[i] - hh) for (dd, hh) in zip(dp[j:i], h[j:i])])
    print(dp[n-1])
int(input())
print(3*(r**2))

### FIXED CODE ###

r=int(input())
print(3*(r**2))
L=[int(x) for x in input().split(" ")
print(L.index(0)+1)

### FIXED CODE ###

L=[int(x) for x in input().split(" ")]
print(L.index(0)+1)
a,b=map(int,input().split())
price=10*b
c=[]  
while(price<=10*b+10):
  if int(price*0.08)==a:
    c.append(a)
  else:
    price=price+1
if c=[]:
  print(-1)
else:
  print(min(c))

### FIXED CODE ###

a,b=map(int,input().split())
price=10*b
c=[]  
while(price<10*b+10):
  if int(price*0.08)==a:
    c.append(price)
    price=price+1
  else:
    price=price+1
if c==[]:
  print(-1)
else:
  print(min(c))
from collections import deque

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[i/2 for i in l]
if n==1:
  if (m//l[0])%2==0:
    print(int((m//l[0])/2))
  else:
    print(int((m//l[0]+1)/2))
  exit()
  
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

l=set(l)
a1=l.pop()
a2=l.pop()
g=gcd(a1,a2)
lcm=g*(a1/g)*(a2/g)
d=1

while l:
  a=l.pop()
  d=gcd(lcm,a)
  lcm=d*(a/d)*(g/d)
  g=lcm
  

if lcm>m:
  print(0)
  exit()
for a in l:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

def lcm(a,b):
    g=math.gcd(a,b)
    return b*(a//g)
l=a[0]//2
for i in range(n):
    r=a[i]//2
    l=lcm(l,r)
for i in range(n):
    if (l//(a[i]//2))%2==0:
        print(0)
        exit()
res=m//l
print((res+1)//2)
N,X = map(int, input().split())
L = list(map(int, input().split()))
i = 0
D = 0
while D <= X and i <= N+1:
    D += L[i]
    i += 1
print(i)

### FIXED CODE ###

N,X = map(int, input().split())
L = list(map(int, input().split()))
D = 0
i = 1
while i - 1 < N:
    #print("D, X", D, X)
    D += L[i-1]
    if X < D:
        break
    i += 1

print(i)
S = int(input(""))

if S >= 0 and S < 86400:
    h = S / 3600
    m = (S % 3600) / 60
    s = ((S % 3600) % 60) % 60

print("{0:d}:{1:d}:{2:d}".format(h, m, s))

### FIXED CODE ###

second = int(input(""))

if second >= 0 and second < 86400:
    h = int(second / 3600)
    m = int((second % 3600) / 60)
    s = int(((second % 3600) % 60) % 60)

print("{0}:{1}:{2}".format(h, m, s))
import re
print(len(max(re.sub(r'[^ACGT]', ' ', input()).split())))

### FIXED CODE ###

row = input()
lenght = len(row)
max_moji = 0
for i in range(lenght):
    if row[i] in 'ACGT':
        moji = 1
        for j in range(i + 1, lenght):
            if row[j] in 'ACGT':
                moji += 1
            else:
                break
        max_moji = moji if moji > max_moji else max_moji
    if max_moji == lenght - i:
        break
print(max_moji)
a = int(input("x")) 
if 1 <= x <= 100:
 print(a**3)
else:
 print("error")


### FIXED CODE ###

x = int(input())
print(x**3)
N = int(input())
xu = [[] for i in range(N)]
otoshidama = 0
for i in range(N):
    xu[i] = list(input().split())
for i in xu:
    if i[1] == 'JPY':
        otoshidama += int(i[0])
    else:
        otoshidama +=

### FIXED CODE ###

N = int(input())
xu = [[] for i in range(N)]
otoshidama = 0
for i in range(N):
    xu[i] = list(input().split())
for i in xu:
    if i[1] == 'JPY':
        otoshidama += int(i[0])
    else:
        otoshidama += float(i[0])*380000
print(otoshidama)
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    c = sorted(c, key=lambda x:x[0]//sum(x[1:]))
    ans = 0
    rikaido = [0]*m
    possible = False
    for i in c:
        ans += i[0]
        for num, val in enumerate(i[1:]):
            rikaido[num] += val

        if min(rikaido) >= x:
            possible = True
            break
    print(ans) if possible else print(-1)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
def main():
    n,m,x = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(n)]
    # c = sorted(c, key=lambda x:sum(x[1:])/x[0], reverse=True)
    ans = 10**9
    possible = False

    for i in range(1, n+1):
        for j in itertools.combinations(c,i):
            rikaido = [0]*m
            kingaku = 0
            for k in j:
                kingaku += k[0]
                for num, val in enumerate(k[1:]):
                    rikaido[num] += val

            if min(rikaido) >= x:
                ans = min(ans, kingaku)
    print(-1) if ans == 10**9 else print(ans)

if __name__ == "__main__":
    main()
import math
a = (int)(input())
b = int(input())
h = int(input())
m = int(input())
t1 = h/6 * math.pi
t2 = m/30 * math.pi
dellt = abs(t2 - t1)
ans = b*b + a*a - 2*a*b*math.cos(dellt)
print(ans**0.5)


### FIXED CODE ###

import math
s = input()
a,b,h,m = s.split(' ')
a = int(a)
b = (int)(b)
h = int(h)
m = int(m)
t1 = h/6 * math.pi + math.pi/6*m/60
t2 = m/30 * math.pi
dellt = abs(t2 - t1)
ans = b*b + a*a - 2*a*b*math.cos(dellt)
print(ans**0.5)
A,B,M = map(int,input().split(","))
a = list(map(int,input().split(",")))
b = list(map(int,input().split(",")))
tmp = 1000000000
for i in range(M):
    c = int(input())
    sum1 = a[i]+b[i]-c
    ans = min(tmp,sum1)
print(ans)

### FIXED CODE ###

A,B,M = map(int,input().split(" "))
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
ans = min(a) + min(b)
for i in range(M):
    x,y,c = map(int,input().split(" "))
    tmp = a[x-1]+b[y-1]-c
    ans = min(tmp,ans)
print(ans)
#
# 149C Next Prime
#
from sympy import nextprime

n = input()
print(nextprime(int(n)-1))

### FIXED CODE ###

#
# 149C Next Prime
#

def isPrime(num):
    if num == 2:
        return True
    for p in range(2, num):
        if  num % p == 0:
            return False
    return True

if __name__ == "__main__":
    n = input()
    num = int(n)
    while True:
        if isPrime(num):
            print(num)
            break
        num += 1
li=[]
a,b,n=map(int,input().split())
for x in range(1,n+1):
    if x%b!=0:
        li.append((a*x)//b-a*(x//b))
print(max(li))


### FIXED CODE ###

a,b,n=map(int,input().split())
print((a*min(n,b-1))//b)
p = [1] * 1000001
for i in range(3, 1001, 2):
    if p[i] == 0:
        continue
    for j in range(2, 1000001/i):
        p[i*j] = 0

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    res = n * (n-1) / 2 + 2
    for j in range(2, n+1):
        if p[j] == 1:
            res -= (n / j - 1) * (j - 1)
    print res

### FIXED CODE ###

count = range(1000001) 
for i in xrange(2, 500001):
    for n in xrange(i*2, 1000001, i):
        count[n] -= (count[i] - 1) 
 
count[1] = 2
for i in xrange(2, 1000001):
    count[i] += count[i-1]

t = int(raw_input())
for i in xrange(t):
    n = int(raw_input())
    print count[n] - n + 1
n, m = map(int, stdin.readline().split())
py = []
for _ in range(m):
  py.append(list(map(int, stdin.readline().split())) + [0])

sortPy = sorted(py, key = lambda x : (x[0], x[1]))
 
d = {}
for i, (p, y, n) in enumerate(sortPy):
  if p in d:
    d[p] += 1
  else:
    d[p] = 1
  sortPy[i][2] = d[p]

for p, y, n in py:
  print(str(p).zfill(6) + str(n).zfill(6))

### FIXED CODE ###

n, m = map(int, input().split())
py = []
for _ in range(m):
  py.append(list(map(int,input().split())) + [0])

sortPy = sorted(py, key = lambda x : (x[0], x[1]))
 
d = {}
for i, (p, y, n) in enumerate(sortPy):
  if p in d:
    d[p] += 1
  else:
    d[p] = 1
  sortPy[i][2] = d[p]

for p, y, n in py:
  print(str(p).zfill(6) + str(n).zfill(6))
N, M = map(int, input().split())

wa = [0] * N
pnt = [0] * N
ac = [False] * N

for _ in range(M):
    tmp = 0
    p, s = list(map(str, input().split()))
    if s == 'WA':
      wa[int(p)] += 1
    elif s == 'AC' and not (ac[int(p)]):
      ac[int(p)] = not (ac[int(p)])
      pnt[int(p)] += wa[int(p)]

print(ac.count(True), sum(pnt))

### FIXED CODE ###

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

wa = [0] * N
pnt = [0] * N
ac = [False] * N

for _ in range(M):
    p, s = list(map(str, input().split()))
    if s == 'WA':
      wa[int(p) - 1] += 1
    elif s == 'AC' and not (ac[int(p) - 1]):
      ac[int(p) - 1] = not (ac[int(p) - 1])
      pnt[int(p) - 1] += wa[int(p) - 1]

print(ac.count(True), sum(pnt))
a,b,c = map(int,input().split())
i = int(0)
l = list()
if a > b:
    maxim = a
else:
    maxim = b
for i in range(1,100):
        if ((a % i) == 0) and ((b % i) == 0):
            l.append(i)
        elif maxim < i:
            break

n = int(len(l))
if c == 1:
    n = n
else:
    n -= c
print(l[n])

### FIXED CODE ###

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

if (b / a) >= c:
    print(c)
elif a > b:
    print(0)
else:
    print(int(b / a))