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

from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def possible(x):
    k = K
    for i in range(N):
        if A[i]*F[i]>x:
            k -= ceil(A[i]-x/F[i])
        if k < 0:
            break
    return k >= 0


l = 0
r = 10**12
for i in range(100):
    m = (l+r)/2
    if possible(m):
        r = m
    else:
        l = m

print(round(m))

### FIXED CODE ###

from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def possible(x):
    k = K
    for i in range(N):
        if A[i]*F[i]>x:
            k -= ceil(A[i]-x/F[i])
        if k < 0:
            break
    return k >= 0


l = 0
r = 10**12
for i in range(45):
    m = (l+r)/2
    if possible(m):
        r = m
    else:
        l = m

print(round(m))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
Sum = 0
for i in range(len(A)):
    if i == 0:
        pass
    elif i == 1:
        Sum += A.pop(0)
    else:
        if i % 2 == 0:
            Sum += A[0]
        else:
            Sum += A.pop(0)
print(Sum)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
Sum = 0
for i in range(len(A)):
    if i == 0:
        pass
    elif i == 1:
        Sum += A.pop()
    else:
        if i % 2 == 0:
            temp = A.pop()
            Sum += temp
        else:
            Sum += temp
print(Sum)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N=int(input())
A=tuple(map(int,input().split()))

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*(2**c))%mod
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N=int(input())
A=tuple(map(int,input().split()))

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)
### BUGGY CODE ###

import math
N = int(input())

ans = list()
for i in range(1, int(math.sqrt(N)+1)):
    for j in range(1, N+1): 
        if i * j == N:
            ans.append(i + j -2) 
        else:
             pass

print(min(ans))

### FIXED CODE ###

import math
N = int(input())

ans = list()
for i in range(int(math.sqrt(N))):
    i += 1
    if N % i ==0:
        j = N//i
        ans.append(i + j -2) 
    else:
        pass

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

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]
d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1
  
ans = 0
for k, v in d.items():
  for i in range(v):
    for j in range(i+1,v):
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]

def helper(s):
  d = {}
  for c in s:
    if c not in d:
      d[c] = 0
    d[c] += 1
  
  return d

def pairs(n):
    return int(n * (n - 1) / 2)

d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1

ans = sum([pairs(v) for v in d.values() if v > 1])
  
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_left(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

### FIXED CODE ###

from bisect import bisect_right
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_right(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_right(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    b_i, c_i = map(int, input().split())
    b.append(b_i)
    c.append(c_i)

res = [0 for _ in range(10 ** 5 + 1)]
for a_i in a:
    res[a_i] += 1

for b_i, c_i in zip(b, c):
    num = res[b_i]
    res[b_i] = 0
    res[c_i] += num

    ans = 0
    for i in range(len(res)):
        ans += i * res[i]
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    b_i, c_i = map(int, input().split())
    b.append(b_i)
    c.append(c_i)


res = {}
for a_i in a:
    if not a_i in res:
        res[a_i] = 0
    res[a_i] += 1

ans = 0
for key, val in res.items():
    ans += key * val

for b_i, c_i in zip(b, c):
    num = res[b_i] if b_i in res else 0
    res[b_i] = 0
    if not c_i in res:
        res[c_i] = 0
    res[c_i] += num

    ans += (c_i - b_i) * num

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

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        k = S-i-j
        if 0<=k<=K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

n,m,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
for i in range(n+1):
  res = k-a[i]
  if res<0:
    break
  for t in range(m,-1,-1):
    if b[t] <= res:
      break
  count = max(count,i+t)

print(count)

### FIXED CODE ###

n,m,k = map(int,input().split())
A = [int(p) for p in input().split()]
B = [int(p) for p in input().split()]
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
t = m
for i in range(n+1):
  if k<a[i]:
    break
  while b[t] > k-a[i]:
    t -= 1
  count = max(count,i+t)

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

input()
iter_ = iter(map(int, input().rstrip("\n").split()))

sum_ = next(iter_)
ans = 0

for num in iter_:
    presum = sum_
    sum_ += num
    while presum * sum_ >= 0:
        sum_ += -1 if presum > 0 else 1
        ans += 1

print(ans)


### FIXED CODE ###

input()
seq = list(map(int, input().rstrip("\n").split()))

iter_ = iter(seq)
ans1 = 0
for i, num in enumerate(iter_):
    if i == 0:
        sum_ = num
        if sum_ > 0:
            pass
        else:
            ans1 += abs(sum_ - 1)
            sum_ = 1
    else:
        sum_ += num
        if i % 2:
            if sum_ < 0:
                pass
            else:
                ans1 += abs(sum_ + 1)
                sum_ = -1
        else:
            if sum_ > 0:
                pass
            else:
                ans1 += abs(sum_ - 1)
                sum_ = 1

iter_ = iter(seq)
ans2 = 0
for i, num in enumerate(iter_):
    if i == 0:
        sum_ = num
        if sum_ < 0:
            pass
        else:
            ans2 += abs(sum_ + 1)
            sum_ = -1
    else:
        sum_ += num
        if i % 2:
            if sum_ > 0:
                pass
            else:
                ans2 += abs(sum_ - 1)
                sum_ = 1
        else:
            if sum_ < 0:
                pass
            else:
                ans2 += abs(sum_ + 1)
                sum_ = -1

print(min(ans1, ans2))
### BUGGY CODE ###

from collections import defaultdict
S = input()
N = len(S)
mod = 10 ** 9 + 7

dp = defaultdict(int)
dp[""] = 1

for s in S:
    newDP = defaultdict(int)
    if s == "?":
        s = "ABC"

    for i in s:
        # 入れない
        newDP[""] += dp[""]
        newDP["A"] += dp["A"]
        newDP["AB"] += dp["AB"]
        newDP["ABC"] += dp["ABC"]
        if i == "A":
            newDP["A"] += dp[""]
            newDP["A"] %= mod
        elif i == "B":
            newDP["AB"] += dp["A"]
            newDP["AB"] %= mod
        else:
            newDP["ABC"] += dp["AB"]
            newDP["ABC"] %= mod
    dp = newDP


print(dp["ABC"])

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

a, ab, abc, n = 0, 0, 0, 1
for s in S:
    if s == "A":
        a += n
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    else:
        a, ab, abc, n = 3 * a + n, 3 * ab + a, 3 * abc + ab, 3 * n
        a %= mod
        ab %= mod
        abc %= mod
        n %= mod

print(abc)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input() 
data = [ tuple(map(int, input().split())) for _ in range(Q) ] 

indexList = []
index = -1
while True:
	index = S.find("AC", index+1)

	if index == -1:
		break
	
	indexList.append(index)

# print(indexList)

for (l, r) in data:
	ls = filter(lambda i: i >= l-1, indexList)
	rs = filter(lambda i: i+1 < r, ls)
	# print(list(rs))
	print(len(list(rs)))


### FIXED CODE ###

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

t = [0] * (N + 1) 

for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

from sys import stdin


def main():
    input = stdin.readline
    S = [input()[:-1]]
    Q = int(input())
    L = []
    R = []
    is_turned = False

    for _ in range(Q):
        query = input()[:-1]
        if query == "1":
            is_turned = not is_turned
        else:
            T, F, C = query.split()
            if is_turned ^ (F == "1"):
                L.insert(0, C)
            else:
                R.append(C)

    if (is_turned):
        print("".join(L + S + R)[::-1])
    else:
        print("".join(L + S + R))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    L = ""
    R = ""
    is_turned = False

    for _ in range(Q):
        Query = input().split()
        if Query[0] == "1":
            is_turned = not is_turned
        else:
            if is_turned ^ (Query[1] == "1"):
                # L.insert(0, Query[2])
                L = Query[2] + L
            else:
                # R.append(Query[2])
                R = R + Query[2]

    if (is_turned):
        print("".join(L + S + R)[::-1])
    else:
        print("".join(L + S + R))


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

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)

### FIXED CODE ###

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
l,r=0,0
for i in range(min(41,k)):
    B=np.zeros(n+1,dtype=np.int64)
    for x,y in enumerate(list(A)):
        l=max(0,x-y)
        r=min(n,x+y+1)
        B[l]+=1
        B[r]-=1
    A=np.cumsum(B[:-1])
print(*A,sep=' ')

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)

    amari = [0] * n
    for i1 in range(n):
        amari[i1] = int(s[i1:]) % 2019
    r = 0
    for j1 in range(n):
        r += amari[:-j1-1].count(0)
        amari = [(i - amari[-j1 - 1]) % 2019 for i in amari]
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

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

def equalCheck(aList, bList):
  checkList = [0] * 10
  for i in range(10):
    for j in range(10):
      if checkList[j] == 0 and aList[i] == bList[j]:
        checkList[j] = 1
  if 0 in checkList:
    return False
  return True

N = int(input())
strList = []
for i in range(N):
  strList.append(input())

count = 0
for i in range(N):
  for j in range(i+1,N):
    if equalCheck(strList[i], strList[j]):
      count += 1
      
print(count)





### FIXED CODE ###

N = int(input())
strList = []
for i in range(N):
  strList.append(input())

count = 0

dict = {}

for i in range(N):
  charList = list(strList[i])
  charList.sort()
  key = "".join(charList)
  if not key in dict:
    dict[key] = 1
  else:
    dict[key] += 1  

# dictが持つvalue値を要素にfor文で回す
count = 0;
for v in dict.values():
  count += (v * (v-1) // 2)
print(count)
### BUGGY CODE ###

def div(n, m):
  if n > m:
    n = m
  d = []
  for i in range(2, n+1):
    if n % i == 0 and m % i == 0:
      for j in d:
        if i % j == 0:
          break
      else:
        d.append(i)
  return d

a, b = map(int, input().split())
lc = div(a,b)
print(len(lc) + 1)


### FIXED CODE ###

import math
def gcd(a, b):
  while b > 0:
    a, b = b, a % b
  return a
def div(a):
  r = []
  i = 2
  k = int(math.sqrt(a))
  while i <= k:
    if a % i == 0:
      r.append(i)
      while a % i == 0:
        a //= i
      k = math.sqrt(a)
    i += 1
  if a > 1:
    r.append(a)
  return r

a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = gcd(a,b)
print(len(div(c))+1)
### BUGGY CODE ###

#167
#d
n,k = map(int, input().split())
ln = list(map(int, input().split()))# まちi にいるとき次に町ln[i-1]へいく

# n,k = 10*4,10**18
# ln = list(range(2,n+1))
# ln.append(1)

visit = [0]*n 
now= 1
visit[0] =1
before =[1]
while max(visit) <= 1:
    now = ln[now -1]
    before.append(now)
    visit[now-1] += 1
roops = before.index(now)
roop_ln = before[roops:-1]
mae = before[:roops]
if k <len(mae):
    print(mae[k])
elif len(mae) <= k :
    t = k- len(mae)
    print(roop_ln[t%len(roop_ln)])
    
    

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [0]*q
for i in range(q):
  a[i] = int(input())
for i in range(n):
  if a.count(i+1) > q-k :
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0]*N
for i in range(Q):
  a = int(input())
  A[a-1]+=1
for j in range(N):
  if A[j] > Q-K :
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

    sum = 0
    for i in range(N):
        for j in range(i+1, N):
           sum += a_list[i] ^ a_list[j]

    print(sum % (10**9+7))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    t = [0]*60

    for a in a_list:
        for count, i in enumerate(reversed(format(a, "b"))):
            if i == "1":
                t[count] += 1

    sum = 0
    for i, count in enumerate(t):
        sum += 2 ** i * count * (N - count)
    print(sum % mod)


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

mod = 10**9+7
frac = [1]*364364
for i in range(2,364364):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*364364
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -364364-1, -1):
    fraci[i] = fraci[i+1] * (364364 + i + 1) % mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

def count(a, b):
    (r1, c1), (r2, c2) = RC[a], RC[b]
    if c2 < c1:
        return 0
    return comb(r2-r1 + c2-c1, r2-r1)

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

RC = [list(map(int, input().split())) for _ in range(N)] + [[1, 1], [H, W]]
RC.sort()

dpe = [0]*(N+2)
dpo = [0]*(N+2)
dpe[0] += 1

for i in range(1, N+2):
    rese = 0
    reso = 0
    for k in range(i):
        rese = (rese + count(k, i)*dpo[k]) % mod
        reso = (reso + count(k, i)*dpe[k]) % mod
    dpe[i] = rese
    dpo[i] = reso

print((dpo[-1] - dpe[-1]) % mod)

### FIXED CODE ###

mod = 10**9+7
frac = [1]*364364
for i in range(2,364364):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*364364
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -364364-1, -1):
    fraci[i] = fraci[i+1] * (364364 + i + 1) % mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

def count(a, b):
    (r1, c1), (r2, c2) = RC[a], RC[b]
    if c2 < c1:
        return 0
    return comb(r2-r1 + c2-c1, r2-r1)

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

RC = [list(map(int, input().split())) for _ in range(N)] + [[1, 1], [H, W]]
RC.sort()

dpe = [0]*(N+2)
dpo = [0]*(N+2)
dpe[0] += 1

for i in range(1, N+2):
    rese = 0
    reso = 0
    for k in range(i):
        t = count(k, i)
        if not t:
            continue
        rese = (rese + t*dpo[k]) % mod
        reso = (reso + t*dpe[k]) % mod
    dpe[i] = rese
    dpo[i] = reso

print((dpo[-1] - dpe[-1]) % mod)
### BUGGY CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k):
    for i in di:
        if k+i>=size:
            continue
        if ans[k]+c[k]<ans[k+i]:
            ans[k+i]-=1
            f(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    f(k)
print(t)

### FIXED CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k,i):
    if k+i>=size:
        return
    if ans[k]+c[k]<ans[k+i]:
        ans[k+i]-=1
        q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k,1)
        f(k,-1)
        f(k,n+1)
        f(k,-n-1)
print(t)
### BUGGY CODE ###

MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    dp = [0]*(X+1)
    dp[X] = 1
    for i in range(N):
        new = [0] * (X+1)
        for x in range(X+1):
            xx = x % S[i]
            new[x] += dp[x] * (N-i-1)
            new[x] %= MOD
            new[xx] += dp[x]
            new[xx] %= MOD
        dp = new

    total = 0
    for x in range(X):
        total += dp[x] * x
        total %= MOD
    print(total)

main()


### FIXED CODE ###

from collections import defaultdict as dd
MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    dp = dd(int)
    dp[X] = 1
    for i in range(N):
        new = dd(int)
        for x in dp:
            xx = x % S[i]
            new[x] += dp[x] * (N-i-1)
            new[x] %= MOD
            new[xx] += dp[x]
            new[xx] %= MOD
        dp = new

    total = 0
    for x in dp:
        total += dp[x] * x
        total %= MOD
    print(total)

main()
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    queries = [input() for _ in range(Q)]

    reverse = False

    for e in queries:
        if e[0] == '1':
            reverse = not reverse
        else:
            T, F, C = e.split()
            if F == '2': F = True
            else: F = False

            if reverse ^ F:
                # 末尾に追加
                S += C
            else:
                # continue
                # 先頭に追加，ここの計算がボトルネック
                S = S[::-1]
                S += C
                reverse = not reverse
        # print(S)

    if reverse:
        S = S[::-1]

    print(S)



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    queries = [input() for _ in range(Q)]

    reverse = False
    front = ""

    for e in queries:
        if e[0] == '1':
            reverse = not reverse
        else:
            T, F, C = e.split()
            if F == '2': F = True
            else: F = False

            if reverse ^ F:
                # 末尾に追加
                S += C
            else:
                # continue
                # 先頭に追加，ここの計算がボトルネック
                front += C
        # print(S)

    if reverse:
        S = S[::-1]
        S = S + front
    else:
        S = front[::-1] + S

    print(S)
    

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

# Atcoder problem Solving

# Code Festival Team Relay
import math

N, K = map(int, input().split())
que = [tuple(map(int, input().split())) for _ in range(N)]


def count(X):
    cnt = 0
    for i in range(N):
        w, d = que[i]
        if X >= w:
            cnt+=(X-w)//d+1
    return cnt


# case_impossible
l = -1

# case_possible

r = 10**25

while r-l > 1:
    m = (l+r)//2
    if count(m) < K:
        l = m
    else:
        r = m

print(r)

### FIXED CODE ###

# Atcoder problem Solving

# Code Festival Team Relay
import math

N, K = map(int, input().split())
que = [tuple(map(int, input().split())) for _ in range(N)]


def count(X):
    cnt = 0
    for i in range(N):
        w, d = que[i]
        if X >= w:
            cnt+=(X-w)//d+1
    return cnt


# case_impossible
l = -1

# case_possible

r = 10**19

while r-l > 1:
    m = (l+r)//2
    if count(m) < K:
        l = m
    else:
        r = m

print(r)