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

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

ans = -10**14

for i in range(N+1):
    left = sorted(A[:N+i])
    right = sorted(A[N+i:])
    diff = sum(left[i:]) - sum(right[:N])
    ans = max(ans, diff)

print(ans)



### FIXED CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
 
L = A[:N]
heapq.heapify(L) 

sum_L = [0] * (N+1)
sum_L[0] = sum(L)

for i in range(N):
    min_L = heapq.heappushpop(L, A[N+i])
    sum_L[i+1] = sum_L[i] + A[N+i] - min_L
    #print(L, i, A[N+i], min_L, sum_L)

R = A[N*2:]
rev_R = list(map(lambda x: x*(-1), R))
heapq.heapify(rev_R) 

sum_R = [0] * (N+1)
sum_R[N] = sum(R)

for i in range(N-1, -1, -1):
    max_R = heapq.heappushpop( rev_R, A[N+i]*(-1) ) * (-1)
    sum_R[i] = sum_R[i+1] + A[N+i] - max_R
    # print(rev_R, i, A[N+i], max_R, sum_R)

ans = -10**14

for i in range(N+1):
    ans = max(ans, sum_L[i] - sum_R[i])

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

R,G,B,N=map(int,input().split())
ans=0
for i in range(N+1):
	for j in range (N+1):
		z=N-(R*i+G*j)
		if z>=0 and z%B==0:
			ans+=1
print(ans)			



### FIXED CODE ###

R,G,B,N=map(int,input().split())
ans=0
for i in range(N+1):
	for j in range (N+1):
		z=N-(R*i+G*j)
		if z>=0 and z%B==0:
			ans+=1
print(ans)
### BUGGY CODE ###

ss=[]
n=int(input())
i=0
while i!=n:

    s=list(input())
    s.sort()
    ss.append(s)
    i+=1
ans=0
i=0
while i!=n:
    s=ss[i]
    ans+=ss.count(s)-1
    i+=1
print(int(ans/2))

### FIXED CODE ###

ss=[]
n=int(input())
i=0
while i!=n:

    s=list(input())
    s.sort()
    ss.append(s)
    i+=1
ans=0
i=1
ss.sort()
mians=0

s=ss[0]
while i!=n:
    if s==ss[i]:
        ans+=1
        mians+=1


    else:
        while mians!=0:
            mians-=1
            ans+=mians
    s=ss[i]
    i += 1
while mians != 0:
    mians -= 1
    ans += mians

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

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()[::-1]

    res = 0
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                res = max(res, min(j - i, dp[i][j]))

    print(res)


if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1

    res = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                now = min(dp[i][j], j - i)
                res = max(res, now)
    print(res)


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

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]
    for i in range(len(L[p])):
        if pre!=L[p][i]:
            dfs(L[p][i],p)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global ans
    ans[p] = ans[pre] + sums[p]
    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


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

b=list(map(int,input().split()))
LL=[]
for i in range(b[0]):
    LL.append(list(map(int,input().split())))
LL.sort(key=lambda x: x[0])
x=0
z=0
y=b[1]
while y>=0 and not LL==[]:
    if y<=LL[0][1]:
        print(x+LL[0][0]*y)
        break
    else:
        y-=LL[0][1]
        x+=LL[0][1]*LL[0][0]
        LL=LL[1:]

### FIXED CODE ###

b=list(map(int,input().split()))
LL=[]
for i in range(b[0]):
    LL.append(list(map(int,input().split())))
LL.sort()
x=0
z=0
y=b[1]
i=-1
while y>=0 and not LL==[]:
    i+=1
    if y<=LL[i][1]:
        print(x+LL[i][0]*y)
        break
    else:
        y-=LL[i][1]
        x+=LL[i][1]*LL[i][0]
### BUGGY CODE ###

from collections import deque

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

move = (-w, -1, 1, w)
todo = deque([])
done = [False for _ in range(w * h)]
grid = ""
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append(j + i * w)
            done[j + i * w] = True
    grid += s
grid = list(grid)

cnt = -1
while todo:
    for i in range(len(todo)):
        n = todo.popleft()
        for dn in move:
            if n % w == 0 and dn == -1:
                pass
            elif n % w == w - 1 and dn == 1:
                pass
            elif n < w and dn == -w:
                pass
            elif n >= w * h - w and dn == w:
                pass
            elif done[n + dn]:
                pass
            elif grid[n + dn] == "#":
                pass
            elif grid[n + dn] == ".":
                todo.append(n + dn)
                done[n + dn] = True
                grid[n + dn] = "#"
    cnt += 1

print(cnt)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "#")
cost = np.full((h, w), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, h):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(h - 1)[::-1]:
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, w):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(w - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    e3 = [[] for _ in range(n)]
    for i in range(n):
        que = collections.deque(e[i])
        for _ in range(2):
            for __ in range(len(que)):
                tmp = que.popleft()
                for ei in e[tmp]:
                    que.append(ei)
        tmp = set(que)
        tmp -= {i}
        e3[i] = list(tmp)

    ans = -1
    cnt = 1
    que = collections.deque(e3[s])
    finflg = True

    while len(que) and finflg and cnt < 10 ** 5+1:

        cnt += 1
        for _ in range(len(que)):
            q = que.popleft()
            for ei in e3[q]:
                que.append(ei)
                if ei == t:
                    finflg = False
                    ans = cnt

    print(ans if ans != -1 else -1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


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

import sys
input = sys.stdin.readline
n,m,s,t = [int(i) for i in input().split()]
es = []
der = []
for i in range(m):
  u,v,a,b = [int(i) for i in input().split()]
  es_append = es.append
  der_append = der.append
  es_append((u-1,v-1,a))
  es_append((v-1,u-1,a))
  der_append((u-1,v-1,b))
  der_append((v-1,u-1,b))
  
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*(n+1)
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])
  
chk = tuple(chk)
for i in range(n):
  print(chk[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")
### BUGGY CODE ###

n,k=map(int,input().split())
i=1
#N進数m桁であらわせる最大値はN**m-1
j=int(k**i)

import sys

while True:

    if n <=(j-1):

        print(i)

        sys.exit()

    else:
        i+=1
        pass


### FIXED CODE ###

n,k=map(int,input().split())
i=0


while n>=k**i:

    i+=1

else:
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sorted(set(A), reverse=True)
w, h = 0, 0

cnt = 0
for s in S:
  c = A.count(s)
  if c > 1:
    if cnt == 0:
      if c > 3:
        w, h = s, s
        cnt += 2
        break
      else:
        w = s
        cnt += 1
    else:
      h = s
      cnt += 1
      break
ans = w * h
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sorted(A, reverse=True)
w, h = 0, 0

cnt = 0
tmp = S[0]
for i in range(N):
  if S[i] == tmp:
    cnt += 1
    if cnt == 2:
      if w == 0:
        w = tmp
        cnt = 0
      else:
        h = tmp
        break
  else:
    cnt = 1
    tmp = S[i]
        
ans = w * h
print(ans)
### BUGGY CODE ###

# coding: utf-8

from itertools import permutations

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[float('inf')] * N for _ in range(N)]

for i in range(N):
    G[i][i] = 0

for i in range(M):
    A, B, C = map(int, raw_input().split())
    G[A-1][B-1] =  G[B-1][A-1] = C

# Warshall–Floyd Algorithm
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]); 

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([G[i[j]][i[j+1]] for j in range(R-1)]))

print ans


### FIXED CODE ###

# coding: utf-8

from itertools import permutations
import Queue

N, M, R = map(int, raw_input().split())
r = [i - 1 for i in map(int, raw_input().split())]

G = [[] for _ in xrange(N)]

for i in range(M):
    A, B, C = map(int, raw_input().split())
    A -= 1; B -= 1;
    G[A].append((B, C))
    G[B].append((A, C))

# dijkstra Algorithm
def dijkstra(s):
    d = [float("inf") for _ in xrange(N)]
    que = Queue.PriorityQueue()
    d[s] = 0
    que.put([0, s])

    while not que.empty():
        p = que.get()
        v = p[1]
        if d[v] < p[0]:
            continue
        for i, j in G[v]:
            if d[i] > d[v] + j:
                d[i] = d[v] + j
                que.put([d[i], i])
    return d

table = {}

for i in r:
    table[i] = dijkstra(i)

ans = float('inf')

for i in permutations(r):
    ans = min(ans, sum([table[i[j]][i[j+1]] for j in xrange(R-1)]))

print ans
### BUGGY CODE ###

import os,io
import collections
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=collections.deque(list(map(int,input().split())))
  m.append(a)
ans=0
count=0
failflag=0
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in range(n):
    if m[i]:
      t=m[i][0]
      if m[t-1]:
        if m[t-1][0]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  for k in r:
    m[k].popleft()
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)
    

### FIXED CODE ###

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    if m[k]:
      previous.add(m[k][-1]-1)
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import math

if __name__ == '__main__':
    a, b, n = map(int, input().split())

    value = 0
    maxValue = 0

    while value <= n:
        res = math.floor((a * value) / b) - a * math.floor(value / b)
        maxValue = max(res, maxValue)
        value += 1
    
    print(maxValue)

### FIXED CODE ###

import math


if __name__ == '__main__':
    a, b, n = map(int, input().split())

    x = min(b-1, n)

    res = math.floor((a*x)/b) - a * math.floor(x/b)
    print(res)
### BUGGY CODE ###

while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = sorted([int(raw_input()) for i in range(n)], reverse = True)
	c = 0
	for i in range(n):
		if r[i] < S/2:
			break
		for j in range(i+1,n):
			if r[i]+r[j] > S:
				c += 1
			else:
				break
	print c

### FIXED CODE ###

R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	d = [int(raw_input()) for i in range(n)]
	r = [0]*R
	for i in set(d): r[i] = d.count(i)
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=1000000000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
def bfs(i,j):
    global h,w,s,dp
    if i>0:
        if dp[i-1][j]>dp[i][j]:
            dp[i-1][j]=dp[i][j]
            bfs(i-1,j)
    if j>0:
        if dp[i][j-1]>dp[i][j]:
            dp[i][j-1]=dp[i][j]
            bfs(i,j-1)
    if i<h-1:
        if dp[i+1][j]>dp[i][j]:
            dp[i+1][j]=dp[i][j]
            bfs(i+1,j)
    if j<w-1:
        if dp[i][j+1]>dp[i][j]:
            dp[i][j+1]=dp[i][j]
            bfs(i,j+1)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w:
                if dp[i+k][j+l]>dp[i][j]+1:
                    dp[i+k][j+l]=dp[i][j]+1
                    bfs(i+k,j+l)

bfs(c[0],c[1])
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

### FIXED CODE ###

#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        if i>0:
            if dp[i-1][j]!=-1:
                if dp[i-1][j]>dp[i][j]:
                    dp[i-1][j]=dp[i][j]
                    now.appendleft([i-1,j])
        if j>0:
            if dp[i][j-1]!=-1:
                if dp[i][j-1]>dp[i][j]:
                    dp[i][j-1]=dp[i][j]
                    now.appendleft([i,j-1])
        if i<h-1:
            if dp[i+1][j]!=-1:
                if dp[i+1][j]>dp[i][j]:
                    dp[i+1][j]=dp[i][j]
                    now.appendleft([i+1,j])
        if j<w-1:
            if dp[i][j+1]!=-1:
                if dp[i][j+1]>dp[i][j]:
                    dp[i][j+1]=dp[i][j]
                    now.appendleft([i,j+1])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w:
                    if dp[i+k][j+l]!=-1:
                        if dp[i+k][j+l]>dp[i][j]+1:
                            dp[i+k][j+l]=dp[i][j]+1
                            now.append([i+k,j+l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)
### BUGGY CODE ###

import sys
from collections import Counter
from math import factorial

N = int(input())
S = input()

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
ct_L = 1
ans = 1
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if op[i-1] == 'L':
            op += 'R'
            ans *= ct_L
            ct_L -= 1
        else:
            op += 'L'
            ct_L += 1
    else:
        if op[i-1] == 'L':
            op += 'L'
            ct_L += 1
        else:
            op += 'R'
            ans *= ct_L
            ct_L -= 1

ct_L, ct_R = Counter(op).values()
if ct_L != ct_R:
    print(0)
    sys.exit()

mod = 10**9+7
print(factorial(N) * ans % mod)


### FIXED CODE ###

import sys
from math import factorial

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

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op += 'R' if op[i-1] == 'L' else 'L'
    else:
        op += 'R' if op[i-1] == 'R' else 'L'

if op.count('L') != N:
    print(0)
    sys.exit()

ct_L, ans = 0, 1

for i in op:
    if i == 'L':
        ct_L += 1
    else:
        ans *= ct_L
        ct_L -= 1
    ans %= mod


print(factorial(N) * ans % mod)
### BUGGY CODE ###

n = input()
arr = map(int, raw_input().split())
new = [0 for i in range(n)]

for i in range(n):
    new[i] = arr.index(i+1)+1

for k in new:
    print k,


### FIXED CODE ###

n = input()
arr = map(int, raw_input().split())
new = [0 for i in range(n)]


for i in range(n):
    new[arr[i]-1] = i+1

for k in new:
    print k,
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
wd = []
for i in range(n):
    w, d = [int(item) for item in input().split()]
    wd.append((w, d))

l = -1; r = 10**20
while r - l > 1:
    mid = (l + r) // 2
    flower = 0
    for w, d in wd:
        if mid - w >= 0:
            flower += (mid - w) // d + 1
        if flower >= k:
            break
    if flower >= k:
        r = mid
    else:
        l = mid
print(r)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
wd = []
for i in range(n):
    w, d = [int(item) for item in input().split()]
    wd.append((w, d))

l = -1; r = 10**20
while r - l > 1:
    mid = (l + r) // 2
    flower = 0
    for w, d in wd:
        if mid - w >= 0:
            flower += (mid - w) // d + 1
        if flower >= k:
            break
    if flower >= k:
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

S=input()
Q=int(input())

# deq=deque()
# for s in S:
#     deq.append(s)

rev=False
front=""
last=""
# ans+=S

for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
        # print(rev)
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            # deq.appendleft(query[2])
            front=query[2]+front
        else:
            # deq.append(query[2])
            last+=query[2]

# if rev:
#     deq.reverse()
# # ans=""
# for i in range(len(deq)):
#     ans+=deq[i]

if not rev:
    print(front+S+last)
else:
    print(last[::-1]+S[::-1]+front[::-1])

### FIXED CODE ###

S=input()
Q=int(input())

# deq=deque()
# for s in S:
#     deq.append(s)

rev=False
front=""
last=""
# ans+=S

for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
        # print(rev)
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            # deq.appendleft(query[2])
            front=query[2]+front
        else:
            # deq.append(query[2])
            last+=query[2]

# if rev:
#     deq.reverse()
# # ans=""
# for i in range(len(deq)):
#     ans+=deq[i]

if not rev:
    print(front+S+last)
else:
    print(last[::-1]+S[::-1]+front[::-1])
### BUGGY CODE ###

##AC
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))
for i in a:
    for j in np.arange(i, max_num, i):
        dp[j] += 1
print(np.count_nonzero(dp[a] == 1))

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in a:
        for j in np.arange(i, max_num, i):
            dp[j] += 1
    print(np.count_nonzero(dp[a] == 1))