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

# -*- coding: utf-8 -*-
 
n,k = map(int, input().split())
 
################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################
 
if k >= n:
  ans = comb(2*n-1, n, p) % p
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, n-i-1, p) % p
    temp2 = comb(n, i, p) % p
    temp = temp * temp2 % p
    ans = (ans + temp) % p
    
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10**9 +7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret *= kaijo(n)
  ret %= MOD;
  ret *= gyaku_kaijo(r)
  ret %= MOD;
  ret *= gyaku_kaijo(n-r)
  ret %= MOD;
  return ret




 
n,k = map(int, input().split())
 
################
#p = 10**9 + 7
#def comb(n,k,p):
#  ans = 1
#  for i in range(1,k+1):
#    ans = ans * (n - (i-1)) % p
#    ans = ans * pow(i, p-2, p)
#  return ans
################
 
if k >= n:
  ans = nCr(2*n-1, n) % MOD
else:
  ans = 0
  for i in range(0,k+1):
    temp = (nCr(n-1, i) % MOD) * (nCr(n, i) % MOD) % MOD
    ans = (ans + temp) % MOD
    
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18 + 1
total = 1
cnt = 0
while cnt < len(A):
    total *= A[cnt]
    cnt += 1
    
if total >= over_value:
    total = -1
print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18
total = 1
cnt = 0
while cnt < N:
    total *= A[cnt]
    if total > over_value:
        total = -1
        break
    cnt += 1
    
for i in range(N):
    if A[i] == 0:
        total = 0
print(total)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
List=[i for i in range(10**5+1)]
Used=[]
for i in range(Q):
    B,C=map(int,input().split())
    List[B]=C
    Used.append(B)
    for i in Used:
        index=i
        while index!=List[index]:
            index=List[index]
            if index==i:
                break
            # print(index)
            # print(List)
        List[i]=index
    ChangedA=[List[a] for a in A]
    print(sum(ChangedA))

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
SUM=sum(A)
Q=int(input())
List=np.array([0 for _ in range(10**5+1)])
for a in A:
    List[a]+=1
for q in range(Q):
    B,C=map(int,input().split())
    SUM-=B*List[B]
    SUM+=C*List[B]
    List[C]+=List[B]
    List[B]=0
    print(SUM)
### BUGGY CODE ###

import math

K = int(input())

sum = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            a = math.gcd(math.gcd(i, j), k)
            # print(math.gcd(math.gcd(i, j), k))
            sum += a

print(sum)


### FIXED CODE ###

import math

K = int(input())

gcds = []

for a in range(1, K + 1):
    for b in range(1, K + 1):
        gcds.append(math.gcd(a, b))

# print(gcds)

ans = 0
for c in range(1, K + 1):
    for g in gcds:
        if c == 1 or g ==1:
            ans += 1
        else:
            ans += math.gcd(c, g)

print(ans)
### BUGGY CODE ###

n=int(input())
d=dict()
for i in range(1,n+1):
  for j in range(1,i+1):
    while i%j==0:
      if j not in d:
        d[j]=1
      else:
        d[j]+=1
      i//=j
ans=1
for i in d.values():
  ans*=i+1
print(ans%1000000007)


### FIXED CODE ###

n=int(input())
d=dict()
for i in range(1,n+1):
  for j in range(1,i+1):
    if j==1:
      continue
    while i%j==0:
      if j not in d:
        d[j]=1
      else:
        d[j]+=1
      i//=j
ans=1
for i in d.values():
  ans*=i+1
print(ans%1000000007)
### BUGGY CODE ###

S = input()

n = len(S)

modlist = [0] * 2019
num = 0

for i in range(n):
    fig = int(S[n - i - 1])
    num += (fig * (10 ** i)) % 2019
    modlist[num % 2019] = modlist[num % 2019] + 1

result = 0
if modlist[0] > 0:
    result += 1

for i in range(2019):
    if modlist[i] != 0:
        result += modlist[i] * (modlist[i] - 1) / 2

print(int(result))

### FIXED CODE ###

S = input()

n = len(S)

medalist = [0] * 2019
medalist[0] = 1
num = 0
mods = 1

for i in range(n):
    fig = int(S[n - i - 1])
    num = (num + fig * mods) % 2019
    medalist[num] = medalist[num] + 1
    mods = (mods * 10) % 2019

result = 0

for i in range(2019):
    m = medalist[i]
    if m != 0:
        result += m * (m - 1) / 2

print(int(result))
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
m = None
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)
    if m is None or m<t: m=t
#
# check
def check_update(r,k,x,m):
    k_ = abs(k-x)
    if r[k_]:
        return True
    k_ = k + x
    if k_<m and r[k_]:
        return True
    return False
    
# initialize
m = m * (h+w-2) + 1
dp = [[[False] * m for _ in range(w)] for _ in range(h)]
dp[0][0][ab[0][0]] = True
for ij in range(1,h+w-1):
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        x = ab[i][j]
        nxt = dp[i][j]
        for k in range(m):
            k1 = abs(k-x)
            k2 = k+x
            if i>0:
                flag = check_update(dp[i-1][j],k,x,m)
                if flag:
                    nxt[k] = True
                    continue
            if j>0:
                flag = check_update(dp[i][j-1],k,x,m)
                if flag:
                    nxt[k] = True
                    continue
# stdout
ref=dp[h-1][w-1]
for k in range(m):
    if ref[k]:
        print(k)
        break


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-1]))
### BUGGY CODE ###

h, w = map(int, input().split())

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i][j] == '#':
            continue
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

print(ans)


### FIXED CODE ###

h, w = map(int, input().split())

mm = ['#' + input() + '#' for i in range(h)]
m = ['#' * (w+2)] + mm + ['#' * (w+2)]

vertical = [[0] * (w+1) for i in range(h+1)]
for i in range(1, h+1):
    c = 0
    for j in range(1, w+2):
        if m[i][j] == '#':
            for k in range(c+1, j):
                vertical[i][k] = j-c-1
            c = j


horizontal = [[0] * (w+1) for i in range(h+1)]
for i in range(1, w+1):
    c = 0
    for j in range(1, h+2):
        if m[j][i] == '#':
            for k in range(c+1, j):
                horizontal[k][i] = j-c-1
            c = j

ans = 1
for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i][j] == '#':
            continue
        ans = max(ans, vertical[i][j] + horizontal[i][j] - 1)

print(ans)
### BUGGY CODE ###

import sys
N = int(input())
S = sys.stdin.readline()
Q = int(input())
ks = list(map(int,input().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')

### FIXED CODE ###

import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')
### BUGGY CODE ###

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    for i in range(N-1):
        if h_list[i]-1 > min(h_list[i+1:]):
            print("No")
            return
    print("Yes")


main()


### FIXED CODE ###

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    h_sort = sorted(h_list)
    for i in range(N-1):
        if h_list[i]-1 > h_sort[i]:
            print("No")
            return
    print("Yes")


main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

pushed = []

while(1):
  pushed.append(i)
  i = a[i]
  count += 1
  if i == 1:
    break
  elif i in pushed:
    count = -1
    break
    
print(count)

### FIXED CODE ###

n = int(input())

a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

for _ in range(n+1):
  i = a[i]
  count += 1
  if i == 1:
    break

if count == n + 1:
  count = -1
  
print(count)
### BUGGY CODE ###

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

tmp = 1
for j in range(K):
    tmp *= A[j]
for i in range(1, N-K+1):
    ans = 1
    for j in range(K):
        ans *= A[i+j]
    # print(tmp, ans)
    if tmp < ans:
        print('Yes')
    else:
        print('No')
    tmp = ans


### FIXED CODE ###

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

for i in range(N-K):
    if A[i] < A[i+K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

# AtCoder Grand Contest 029
# December 15, 2018
#

#S = 'BWBWBW'
S = input()
N = len(S)

buf = []
for s in S:
  if s == 'B':
    buf.append(0)
  else:
    buf.append(1)

count = 0
flag = True
#print(buf)

while flag:
  for i in range(N-1):
    if buf[i] == 0 and buf[i+1] == 1:
      buf[i] = 1
      buf[i+1] = 0
      #print(buf)
      count += 1
      break
  else:
    flag = False

print(count)


### FIXED CODE ###

S = input()
N = len(S)

count = 0
num = 0
idx = -1
while True:
  idx = S.find('W', idx + 1)
  if idx < 0:
    break
  count += idx - num
  num += 1

print(count)
### BUGGY CODE ###

from collections import defaultdict
s = input()
dct = defaultdict(int)
dct[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x += int(c)*d
    dct[x%2019] += 1
    d *= 10
ans = 0
for v in dct.values():ans += v*(v-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
s = input()
mod = 2019
dct = defaultdict(int)
dct[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x = (x+int(c)*d)%mod
    d = d*10%mod
    dct[x] += 1
ans = 0
for v in dct.values():ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

A, B = map(int,input().split())
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0: return a
    r = a % b
    return gcd(b,r)

L = []

g = gcd(A, B)
i = 2
while g > 1:
    if g % i == 0:
        L.append(i)
        g /= i
    else:
        i += 1
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(L)
print(len(c) + 1)



### FIXED CODE ###

A, B = map(int,input().split())
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0: return a
    r = a % b
    return gcd(b,r)

L = [1]

g = gcd(A, B)
g_copy = gcd(A, B)
i = 2
while g > 1:
    if i > g_copy ** (1/2) :
        if g != 1:
            L.append(i)
        break
    if g % i == 0:
        if L[-1] != i:
            L.append(i)
        g /= i
    else:
        i += 1
print(len(L))
### BUGGY CODE ###

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

def tri_judge(a,b,c):
    if a<b+c and b<c+a and c<a+b:
        return 1
    else:
        return 0
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        check = L[i]+L[j]
        for k in range(j+1,n):
            if check>L[k]:
                if(tri_judge(L[i],L[j],L[k])):
                    cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int,input().split())))
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        cnt += bisect.bisect_left(L,L[i]+L[j])-(j+1)
print(cnt)
### BUGGY CODE ###

n = int(input())
nums = str(input())
nums = nums.split()
judge = 0
for i in range(n):
  for j in range(i+1,n):
    if nums[i] == nums[j]:
      judge = 1
if judge == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n = int(input())
a = input().split()
a = sorted(list(map(int, a)))
def check(a):
    for i in range(n-1):
        if a[i] == a[i+1]:
            return 0
    return 1
if check(a) == 0:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  if x==0:
    return 0
  while y!=0:
    x,y=y,x%y
  return x
 
n = int(input())
a = list(map(int, input().split()))
b = [0]
 
for i in range(n):
  a[i],a[n-1]=a[n-1],a[i]
  temp = a[0]
  for j in range(n-1):
    temp=gcd(temp,a[j])
    if temp < max(b):
      break
  b.append(temp)
  a[i],a[n-1]=a[n-1],a[i]
  
print(max(b))

### FIXED CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x

n = int(input())
a = list(map(int, input().split()))
b = []
l = [0]
r = [0]

for i in range(n):
  l.append(gcd(a[i],l[i]))
  r.append(gcd(a[n-1-i],r[i]))

for i in range(n):
  b.append(gcd(l[i],r[n-1-i]))
  
print(max(b))
### BUGGY CODE ###

A = input()[::-1]
A = "0" + A
# lis_num = [int(s) for s in A]

# print(lis_num)

# S = [0] * len(lis_num)
S = [0] * len(A)
cnt = [0] * 2019
cnt[0] = 1

for i in range(len(A) - 1):
    S[i + 1] = S[i] + int(A[i + 1]) * pow(10, i)
    cnt[S[i + 1] % 2019] += 1

# print(S)


# for i in S:
#     cnt[i % 2019] += 1

ans = 0

for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2

print(ans)


### FIXED CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, 2019)) % 2019
        cnt[S[i + 1] % 2019] += 1

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in cnt:
        ans += i * (i - 1) // 2

    print(ans)


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

import sys
from collections import defaultdict
from itertools import accumulate


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


n = int(sys.stdin.buffer.readline())
mp = map(int, sys.stdin.buffer.read().split())
ab = list(zip(mp, mp))
atob = defaultdict(list)
max_a, max_b = 0, 0
for a, b in ab:
    atob[a].append(b)
    max_a = max(max_a, a)
    max_b = max(max_b, b)

MOD = 10 ** 9 + 7

dp = [0] * (max_b * 2 + 1)
ans = 0
for i in range(-max_a, max_a + 1):
    if i < 0 and -i in atob:
        for j in atob[-i]:
            dp[-j + max_b] += 1
    dp = [x % MOD for x in accumulate(dp)]
    if i > 0 and i in atob:
        for j in atob[i]:
            ans = (ans + dp[j + max_b]) % MOD

facts, invs = prepare(2 * (max_a + max_b), MOD)
ans = int(ans)
for a, b in ab:
    ans = (ans - facts[2 * (a + b)] * invs[2 * a] * invs[2 * b]) % MOD

print(ans * invs[2] % MOD)


### FIXED CODE ###

import sys
from collections import defaultdict

import numpy as np


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


n = int(sys.stdin.buffer.readline())
mp = map(int, sys.stdin.buffer.read().split())
ab = list(zip(mp, mp))
atob = defaultdict(list)
max_a, max_b = 0, 0
for a, b in ab:
    atob[a].append(b)
    max_a = max(max_a, a)
    max_b = max(max_b, b)

MOD = 10 ** 9 + 7

dp = np.zeros(max_b * 2 + 1, dtype=np.int64)
ans = 0
for i in range(-max_a, max_a + 1):
    if i < 0 and -i in atob:
        for j in atob[-i]:
            dp[-j + max_b] += 1
    dp = np.add.accumulate(dp) % MOD
    if i > 0 and i in atob:
        for j in atob[i]:
            ans = (ans + dp[j + max_b]) % MOD

facts, invs = prepare(2 * (max_a + max_b), MOD)
ans = int(ans)
for a, b in ab:
    ans = (ans - facts[2 * (a + b)] * invs[2 * a] * invs[2 * b]) % MOD

print(ans * invs[2] % MOD)
### BUGGY CODE ###

N, M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))

list = [0] * (N+1)

saitan = [1]
for _ in range(M):
    next = []
    for i in range(len(AB)):
        if AB[i][0] in saitan:
            if list[AB[i][1]] == 0:
                list[AB[i][1]] = AB[i][0]
                next.append(AB[i][1])
        if AB[i][1] in saitan:
            if list[AB[i][0]] == 0:
                list[AB[i][0]] = AB[i][1]
                next.append(AB[i][0])
    saitan.extend(next)


print("Yes")
for ele in list[2:]:
    print(ele)


### FIXED CODE ###

from collections import deque

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

graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N+1)
dist[0] = 0
dist[1] = 0

d = deque()
d.append(1)

ans = [0] * (N+1)
while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v]+1
        d.append(i)
        ans[i] = v

print("Yes")
print(*ans[2:], sep='\n')
### BUGGY CODE ###

from collections import defaultdict


def dfs(v):
    stack.append(v)
    global ret
    if ret:
        return
    if v == 2 and len(used) == cnt:
        ret = True
        return
    for idx, u in enumerate(edges[v]):
        tmp = tuple(sorted((u, v)) + [idx])
        if tmp in used:
            continue
        used.add(tmp)
        dfs(u)
        used.discard(tmp)
    stack.pop()

while 1:
    edges = defaultdict(list)
    cnt = 0
    try:
        a, b = map(int, raw_input().split())
        edges[a].append(b)
        edges[b].append(a)
        cnt += 1
    except EOFError:
        break
    while 1:
        a, b = map(int, raw_input().split())
        if a == b == 0:
            break
        edges[a].append(b)
        edges[b].append(a)
        cnt += 1
    stack = []
    ret = False
    used = set()
    dfs(1)
    if ret:
        print "OK"
    else:
        print "NG"

### FIXED CODE ###

while 1:
    edges = [0] * 101
    try:
        a, b = map(int, raw_input().split())
        edges[a] += 1
        edges[b] += 1
    except EOFError:
        break
    while 1:
        a, b = map(int, raw_input().split())
        if a == b == 0:
            break
        edges[a] += 1
        edges[b] += 1
    if edges[1] % 2 and edges[2] % 2 and all(map(lambda a: a % 2 == 0, edges[3:])):
        print "OK"
    else:
        print "NG"
### BUGGY CODE ###

from math import ceil
N = int(input())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)

# print(" ", A, B)

# 後ろから順番にすれば良い気がする (iのボタンは1からiまでしか作用しないので)
count = 0
for j in range(N - 1, -1, -1):
    # j番目の足りない回数を決定
    if A[j] % B[j] == 0:
        continue
    if A[j] < B[j]:
        cj = B[j] - A[j]
    else:
        cj = ((A[j] + B[j] - 1) // B[j]) * B[j] - A[j]
    count += cj

    # cj回押した回数，数値を反映
    for k in range(j, -1, -1):
        A[k] += cj

    # print(j, cj, A, B)
print(count)

### FIXED CODE ###

from math import ceil
N = int(input())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)

# 回数だけ確定する
# 後ろから順番にすれば良い気がする (iのボタンは1からiまでしか作用しないので)
count = 0
for j in range(N - 1, -1, -1):
    if (count + A[j]) % B[j] == 0:
        continue
    else:
        # 足りない分をカウントする
        count += B[j] - (count + A[j]) % B[j]
print(count)
### BUGGY CODE ###

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

li=[]
base=[]
count=1

for i in range(2,fractions.gcd(A,B)+1):
    if min(A,B)%i==0 and max(A,B)%i==0:
        li.append(i)
        if max(A,B)%(min(A,B)//i)==0:
            li.append(min(A,B)//i)
li=sorted(li)
for l in li:
    judge=True
    for k in base:
        if l%k==0:
            judge=False
            break
    if judge==True:
        count+=1
        base.append(l)
print(count)
    

### FIXED CODE ###

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

base=fractions.gcd(A,B)
count=1


for i in range(2,int(pow(base,1/2)+1)):
    if base==1:
        break
    else:
        if base%i==0:
            count+=1
            while base%i==0:
                base//=i
if base!=1:
    count+=1
print(count)
### BUGGY CODE ###

s = input()
s_len = int(len(s))
count = 0
n = int(s_len*(s_len+1)/4)
for _ in range(n):
  num = s.count('BW')
  if num == 0:
    break
  s = s.replace('BW','WB',int(s_len/2))
  count += num
print(count)

### FIXED CODE ###

S = list(input())
W_i = [i for i,j in enumerate(S) if j == 'W']
W_n = S.count('W')
cur = 0
ans = 0
for i in W_i:
  ans += i-cur
  cur += 1
print(ans)
### BUGGY CODE ###

from math import ceil
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort(reverse=True)
    C.sort()
    def chk(x):
        cnt = 0
        for i in range(N):
            cnt += max(ceil(A[i]-x/C[i]), 0)
            if cnt > K:
                return False
        return True
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(m):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import ceil
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort(reverse=True)
    C.sort()
    def chk(x):
        cnt = 0
        for i in range(N):
            cnt += max(ceil(A[i]-x/C[i]), 0)
            if cnt > K:
                return False
        return True
    ng, ok = -1, 10**12
    while ok - ng > 1:
        m = (ok+ng)//2
        if chk(m):
            ok = m
        else:
            ng = m
    print(ok)
if __name__ == "__main__":
    main()