Harryxun/stf_run huggingface dataset:
n = int(input())
s = []
for i in range(n):
    s.append(input())
ans = 0
r = 0
l = 0
a = 0
b = 0
c = 0
for i in range(n):
    ans += s[i].count('AB')
    list = s[i]
    if list[-1] == 'A' and list[0] == 'B':
        r += 1
        l += 1
        c += 1
    elif list[-1] == 'A': # and list[0] != 'B':
        r += 1
        a += 1
    elif list[0] == 'B': # and list[-1] != 'A':
        l += 1
        b += 1
    # print(ans, last, start)
ans += min(r, start)
if a == 0 and b == 0 and c > 0:
    ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
ans = 0
r = 0
l = 0
a = 0
b = 0
c = 0
for i in range(n):
    ans += s[i].count('AB')
    list = s[i]
    if list[-1] == 'A' and list[0] == 'B':
        r += 1
        l += 1
        c += 1
    elif list[-1] == 'A': # and list[0] != 'B':
        r += 1
        a += 1
    elif list[0] == 'B': # and list[-1] != 'A':
        l += 1
        b += 1
    # print(ans, last, start)
ans += min(r, l)
if a == 0 and b == 0 and c > 0:
    ans -= 1
print(ans)
N = int(input())
S = str(input())
T = str(input())

f = ''
for i in range(N):
    f += S[i]
    f += T[i]
print(f)

### FIXED CODE ###

N = int(input())
S,T=map(str, input().split())
f = ''
for i in range(N):
    f += S[i]
    f += T[i]
print(f)
import pdb
import builtins
import sys
import numpy as np
class Test:
    def __init__(self):
        pass

class CustomUtils:
    def __init__(self):
        pass
    def to_int(self, inputs, sp=' '):
        if sp == '':
            return [int(d) for d in list(inputs)]
        else:
            # return map(int,input().split())
            return [int(d) for d in inputs.split(sp)]
    def debug_print(self, inputs, debug=False):
        if debug:
            print(inputs)

# 引用　python する man,「Pythonでの再帰関数とメモ化」, PSM, ２０１７、７/４
# http://muromura.hatenablog.com/entry/2017/07/04/204908#%E3%83%A1%E3%83%A2%E5%8C%96
def memorize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
debug = False

u = CustomUtils()

n, q = u.to_int(input())
s = input()

import re

ss = []
m = re.finditer('AC', s)
for match in m:
    st, en= match.span()
    ss.append(st)
ss.sort()
ss = np.array(ss)

# そこまでに含まれるACの数を返す。
@memorize
def accumulative(i):
    if i == -1:
        return 0
    elif i -1 in ss:
        return accumulative(i-1)+1
    else:
        return accumulative(i-1)
    
total = len(ss)

for _ in range(q):
    # n文字目とindexがずれた。
    l, r = [int(x)  - 1 for x in input().split()]
    result = accumulative(r) - accumulative(l)
    # ちょうどindexlまでに含まれるACの数が、境界をまたぐ数。
    print("{}".format(result))

### FIXED CODE ###

class Test:
    def __init__(self):
        pass

class CustomUtils:
    def __init__(self):
        pass
    def to_int(self, inputs, sp=' '):
        if sp == '':
            return [int(d) for d in list(inputs)]
        else:
            return [int(d) for d in inputs.split(sp)]
    def debug_print(self, inputs, debug=False):
        if debug:
            print(inputs)

# 引用　python する man,「Pythonでの再帰関数とメモ化」, PSM, ２０１７、７/４
# http://muromura.hatenablog.com/entry/2017/07/04/204908#%E3%83%A1%E3%83%A2%E5%8C%96
def memorize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
debug = False



iarray = ['A', 'C', 'G', 'T']
oarray = ['T', 'G', 'C', 'A']
idx = iarray.index(input())

print("{}".format(oarray[idx]))
#ABC167-C
import numpy as np
flg = True
n,m,x = map(int,input().split())
algo = []
tmp = []
for _ in range(n):
    algo.append(list(map(int,input().split())))
    
book = list(itertools.product([0,1],repeat=n))
abi = [0 for _ in range(m)]

for pattern in book:
    #値の初期化
    abi = [0 for _ in range(m)]
    money = 0
    flg = True
    
    for i in range(len(pattern)):
        for j in range(m):
            abi[j] += algo[i][j+1] * pattern[i]
        money += algo[i][0] * pattern[i]
        
    abi_min = [p for p in abi if p < x]
        
    if len(abi_min) != 0:
        flg = False
    if flg:
        print(money)
        tmp.append(money)

if len(tmp) > 0:
    print(min(tmp))
else:
    print(-1)
        
        
        
        
                
            

### FIXED CODE ###

#ABC167-C
import itertools
flg = True
n,m,x = map(int,input().split())
algo = []
tmp = []
for _ in range(n):
    algo.append(list(map(int,input().split())))
    
book = list(itertools.product([0,1],repeat=n))
abi = [0 for _ in range(m)]

for pattern in book:
    #値の初期化
    abi = [0 for _ in range(m)]
    money = 0
    flg = True
    
    for i in range(len(pattern)):
        for j in range(m):
            abi[j] += algo[i][j+1] * pattern[i]
        money += algo[i][0] * pattern[i]
        
    abi_min = [p for p in abi if p < x]
        
    if len(abi_min) != 0:
        flg = False
    if flg:
        tmp.append(money)

if len(tmp) > 0:
    print(min(tmp))
else:
    print(-1)
def func(i, routes, marks):
    update_rooms = []
    if i not in routes:
        return marks
    for j in routes[i]:
        room_idx = j
        if room_idx in marks:
            continue
        marks[room_idx] = i
        update_rooms.append(room_idx)
    for j in update_rooms:
        marks = func(j, routes, marks)
    return marks

def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
    marks = func(0, routes, {0: 0})
try:
    write_result(marks, N)
except:
    pass


### FIXED CODE ###


def get_input():
    N, M =  list(map(int, input().split()))
    routes = {}
    for i in range(M):
        a, b =  list(map(int, input().split()))
        a_idx = a - 1
        b_idx = b - 1
        if a_idx in routes:
            routes[a_idx].append(b_idx)
        else:
            routes[a_idx] = [b_idx]
        
        if b_idx in routes:
            routes[b_idx].append(a_idx)
        else:
            routes[b_idx] = [a_idx]

    return N, M, routes

def write_result(marks, N):
    flag = True
    output_str = ''
    for i in range(1, N):
        if i not in marks:
            flag = False
            break
        output_str += f'{marks[i]+1}\n'
    if flag:
        print('Yes')    
        print(output_str)
    else:
        print('No')

import numpy


marks = {0:0}

N, M, routes = get_input()
mark = {0:0}
start_nodes = [0]
while start_nodes:
    next_nodes = []
    for i in start_nodes:
        for n in routes[i]:
            if n in marks:
                continue
            marks[n] = i
            next_nodes.append(n)
    start_nodes = next_nodes   
write_result(marks, N)
(B + C - A) if (B + C) > A else 0

### FIXED CODE ###

A, B, C = map(int, input().split())
print((B + C - A) if (B + C) > A else 0)
a = int(input().split())
if a[0] <= 5:
  print(0)
elif a[0] <= 12:
  print(a[1]/2)
else:
  print(a[0])

### FIXED CODE ###

a = list(map(int,input().split()))
if a[0] <= 5:
  print(0)
elif a[0] <= 12:
  print(a[1]//2)
else:
  print(a[1])
s=input()

if "h" in s:
    flag = False
    for i in range(len(s)-1):
        if s[i]=="h":
            if s[i+1]=="i":
                flag=True
            else:
                flag=False

if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
if s=="hi" or s=="hihi" or s=="hihihi" or s=="hihihihi" or s=="hihihihihi":
    print("Yes")
else:
    print("No")
sys.setrecursionlimit(1000000)
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[-1 for _ in range(13)] for _ in range(len(S))]


def calc(i, m):  # i桁目以下で余りがmとなるようにする
    if mem[i][m] >= 0:
        return mem[i][m]
    t = S[L - i]
    if t == '?':
        if i == 0:
            if m < 10:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += calc(i - 1, tm)
            mem[i][m] = s
            return s
    else:
        tn = int(t)
        if i == 0:
            if m == tn:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            tm = m - ((Ls[i % 6] * tn) % 13)
            if tm < 0:
                tm += 13
            k = calc(i - 1, tm)
            mem[i][m] = k
            return k


print(calc(len(S) - 1, 5) % (10 ** 9 + 7))

### FIXED CODE ###

S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s % C
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm] % C
print(mem[len(S) - 1][5])
n = int(input())
mod = 10**9+7
dp = [1]*(n+1)
for i in range(3):
    dp[i] = 0

for j in range(3, 10):
    if j <= n:
        dp[j] = 1

for i in range(3, n+1):
    for j in range(3, n):
        if i+j <= n:
            dp[i+j] += dp[i]
            dp[i+j] %= mod
print(dp[-1])


### FIXED CODE ###

n = int(input())
mod = 10**9+7
dp = [1]*(n+1)
if n <= 2:
    print(0)
    exit()
for i in range(3):
    dp[i] = 0

for j in range(3, 10):
    if j <= n:
        dp[j] = 1

for i in range(3, n+1):
    for j in range(3, n):
        if i+j <= n:
            dp[i+j] += dp[i]
            dp[i+j] %= mod
print(dp[-1])
def zen(s):
    ans=0
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            ans+=1
        if len(s)-1==ans:
            return True
        else:
            return False

s=input()
k=int(input())
l=0
cnt=[]
ans=0
p=1
c=1
if zen(s):
    print(len(s)*k//2)
else:
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            c+=1
        else:
            cnt.append(c)
            c=1
        if i==len(s)-2:
            cnt.append(c)
    ans=0
    if s[0]==s[-1] and cnt[-1]%2==1 and cnt[0]%2==1:
        for i in range(len(cnt)):
            ans+=cnt[i]//2
        print(ans*k+(k-1))
    else:
        for i in range(len(cnt)):
            ans+=cnt[i]//2
        print(ans*k)

### FIXED CODE ###

def is_all(t):
    for i in range(len(t)-1):
        if t[i]!=t[i+1]:
            return False
    return True

s=input()
n=len(s)
k=int(input())
cor=[1]
ans=0
c=1
if is_all(s):
    print(n*k//2)
    exit()
i=0
while i<n-1:
    if s[i]==s[i+1]:
        cor[0]+=1
        i+=1
    else:
        i+=1
        break
while i<n-1:
    if s[i]==s[i+1]:
        cor.append(1)
        while i<n-1:
            if s[i]==s[i+1]:
                cor[-1]+=1
                i+=1
            else:
                break
    i+=1
#print(cor)
if s[0]==s[-1]:
    for i in range(1,len(cor)-1):
        ans+=cor[i]//2
    ans*=k
    ans+=(cor[0]+cor[-1])//2*(k-1)
    print(ans+cor[0]//2+cor[-1]//2)
else:
    for i in range(len(cor)):
        ans+=cor[i]//2
    print(ans*k)
a,b,c,d=map(int,input().split())
while True:
  c-=b
  if c<=0:
    print('Yes')
    break
  a-=d
  if a<=0:
    print('No')
    break

### FIXED CODE ###

S,W=map(int,input().split())

if S>W:
  print('safe')
else:
  print('unsafe')
import sys
import math
lines = sys.stdin.readlines()
line1 = lines.pop(0).split(' ')
#print(line1)
N = int(line1[0])
M = int(line1[1])

#print(N)
#print(M)

str = [10] * N
#print(str)
ans = []
flg = 0
flg2 = 0
for i in range(M):
  line = lines.pop(0).split(' ')
#  print(line)
  s = int(line[0])
  c = int(line[1])
#  print(s)
#  print(c)
#  print(str[s-1])
  if str[s-1] > c:
    str[s-1] = c

#print(str)
str = [0 if i == 10 else i for i in str]
#print(str)
if N == 3:
  ret = (int(str[0])*100 + int(str[1])*10 + int(str[2])) if int(str[0]) > 0 else -1
elif N ==2:
  ret = (int(str[0])*10 + int(str[1])) if int(str[0]) > 0 else -1
elif N ==1:
  ret = int(str[0])

print(ret)

### FIXED CODE ###

import math
print(math.ceil(int(input()) / 2))
S = [int(e) for e in input().split()]
list_a =  [int(e) for e in input().split()]
list_b =  [int(e) for e in input().split()]

dis_list = []

for i in range(S[2]):
    dis_list.append([int(e) for e in input().split()])

cost_list = []

for i in list_a:
    for j in list_b:
        cost_list.append(i+j)

### FIXED CODE ###

S = list(input())

word_num = int(len(S)/2)

temp_num = 0

if len(S) % 2 == 0:
    for i in range(word_num):
        if S[2*i]+S[2*i+1] == 'hi':
            pass
        else:
            temp_num += 1
else:
    pass

if len(S) % 2 == 0 and temp_num == 0:
    print('Yes')
else:
    print('No')
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k,t = LI()
    a = LI()
    q = []
    for i in a:
        heappush(q,-i)
    while len(q) > 1:
        x = heappop(q)
        if not q:
            heappush(q,x)
            break
        y = heappop(q)
        x += 1
        y += 1
        if x:
            heappush(q,x)
        if y:
            heappush(q,y)
    print(-q[0]-1)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k,t = LI()
    a = LI()
    q = []
    for i in a:
        heappush(q,-i)
    while len(q) > 1:
        x = heappop(q)
        y = heappop(q)
        x += 1
        y += 1
        if x:
            heappush(q,x)
        if y:
            heappush(q,y)
    if not q:
        print(0)
    else:
        print(-q[0]-1)
    return

#Solve
if __name__ == "__main__":
    solve()
import fractions
N = int(input())
array = list(map(int, input().split()))
array.sort()
ans = array[0]
for i in range(1,ans):
	ans = fractions.gcd(ans,array[i])
print(ans)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
array.sort()
min = array[0]
while True:
	tmp2 = min
	for item in array:
		tmp = item % min
		if tmp != 0 and tmp < min:
			min = tmp
	if min == tmp2:
		break
print(min)
S=input()
T=input()
ANS=[]
for start in range(len(S)-len(T)):
  ans = 0
  for j in range(len(T)):
    if S[start+j] != T[j]:
      ans += 1
  ANS.append(ans)
print(min(ANS))
  

### FIXED CODE ###

S = input()
T = input()
ans = len(T)
for start in range(len(S) - len(T) + 1):
  dif = 0
  for i in range(len(T)):
    if T[i] != S[start + i]:
      dif += 1
  ans = min(ans, dif) 
print(ans)
n=int(input())
a=[int() for i in input().split()]
b=0
for j in range(n):
  for k in range(n):
    if a[j]==a[k] and j!=k:
      b+=1
　　break
if b==0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
for j in range(n-1):
	if a[j]<a[j+1]:
		pass
	else:
		print('NO')
		exit()
print('YES')
a,b.c = [int(c) for c in input()]
i = c * 100 + b * 10 + a
if i % 4 == 0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,b,c = [int(c) for c in input().split(' ')]
i = a * 100 + b * 10 + c
if i % 4 == 0:
  print('YES')
else:
  print('NO')
n,m=map(int, input().split())

g=[[] for i in range(n)]
x=[[] for i in range(m)]

count=0
ans=0
for i in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    x[i]=[u,v]
    
memo=[False for i in range(n)]

def dfs(now,prev):
    for next in g[now]:
        if next!=prev:
            if memo[next]==True:
                continue
            else:
                memo[next]=True
                dfs(next,now)


for i in range(m):
    g[x[i][0]].remove(x[i][1])
    g[x[i][1]].remove(x[i][0])
    for j in range(n):
        memo[j]=True
        dfs(j,-1)
        ans+=memo.count(False)
        memo=[False for i in range(n)]
    print(ans//2)
    ans=0

    
    
    
    
    




### FIXED CODE ###

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod

def comb(n):
    x=1
    y=1
    for i in range(2):
        x*=(n-i)
        y*=(i+1)
    return x//y


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
b = [[] for i in range(n)]
uf = UnionFind(n)

ans=[]
x=comb(n)
for i in range(m):
    ans.append(x)
    if uf.same(a[m-i-1][0]-1,a[m-i-1][1]-1):
        uf.union(a[m-i-1][0]-1,a[m-i-1][1]-1)
    else:
        x-=uf.size(a[m-i-1][0]-1)*uf.size(a[m-i-1][1]-1)
        uf.union(a[m-i-1][0]-1,a[m-i-1][1]-1)
for i in range(m):
    print(ans[-1-i])
N = int(input())
T = [int(input() for _ in range(N))]

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

def lcm(a,b):
    return a*b//gcd(a,b)

ans=1
for i in range(T):
    ans = lcm(ans,i)

print(ans)


### FIXED CODE ###

N = int(input())
T = [int(input()) for _ in range(N)]

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

def lcm(a,b):
    return a*b//gcd(a,b)

ans=1
for i in T:
    ans = lcm(ans,i)

print(ans)
import sys
from math import gcd
input = sys.stdin.buffer.readline

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


def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

p = primes(1003)

g = a[0]
for e in a:
    g = gcd(g,e)

if g != 1:
    print("not coprime")
else:
    a.sort()
    if a[0] == a[-1] and a[0] == 1:
        print("pairwise coprime")
    else:
        s = set()
        for e in a:
            for d in p:
                if e%d == 0:
                    if d in s:
                        print("setwise coprime")
                        exit()
                    s.add(d)
            s.add(e)
        print("pairwise coprime")


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

d,t,s = map(int,input().split())

if t*s >= d:
    print("Yes")
else:
    print("No")
from operator import mul
from functools import reduce

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

def cmb(n,r,mod):
  if r==0 or n==r:return 1
  r = min(n-r,r)
  ue = reduce(mul, range(n, n-r, -1))
  shita = reduce(mul, range(1,r+1))
  return (ue//shita)%mod

for i in range(1,k+1):
  print(cmb(n-k+1,i,mod)*cmb(k-1,k-i,mod)%mod)

### FIXED CODE ###

from operator import mul
from functools import reduce

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

def cmb(n,r,mod):
  if r==0 or n==r:return 1
  r = min(n-r,r)
  ue = reduce(mul, range(n, n-r, -1))
  shita = reduce(mul, range(1,r+1))
  return (ue//shita)%mod

for i in range(1,k+1):
  try:print(cmb(n-k+1,i,mod)*cmb(k-1,k-i,mod)%mod)
  except:print(0)
import sys

def jeat(a, f, x, K):
    N = 0
    for i in range(len(a)):
        if a[i]*f[i] > x:
            N += a[i] - x // f[i]
    if N > K:
        return False
    if N <= K:
        return True

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
F = list(map(int, input().split(' ')))
if K >= sum(A):
    print(0)
    sys.exit()
A.sort()
F.sort(reverse = True)
a = 0
b = 10**13
while (True):
    z = (a+b)//2
    if jeat(A,F,z,K) == True:
        if jeat(A,F,z-1,K) == False:
            break
        b = z-1
    else:
        if jeat(A,F,z+1,K) == True:
            z += 1
            break
        a = z+1

print(z)

### FIXED CODE ###

x,y=map(int,input().split())
if x<=9 and y<=9:
  print(x*y)
else:
  print(-1)
a = list(map(int(input().split()))
n = len(a)-1
i = 0
for _ in range(len(a)-1):
    temp = a[i]
    a[i] = a[n-1]
    a[n-1] = temp
    n+=1
for  i in a:
         print(i,end=" ")

### FIXED CODE ###

a = list(map(int,input().split()))
n = len(a)-1
i = 0
for _ in range(len(a)-1):
    temp = a[i]
    a[i] = a[n-1]
    a[n-1] = temp
    n+=1
for  i in a:
         print(i,end=" ")