CodeEff/ECCO huggingface dataset:
# Original solution
n, k = list(map(int, input().split()))


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):
    index = ps[i] - 1
    value = cs[index]

    searchI = 0
    while True:
        vg = vGraphs[searchI]
        if value in vg:
            currentGraph = vg
            break
        searchI += 1

    total = sum(currentGraph)

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // len(currentGraph)
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

# Optimized solution
n, k = list(map(int, input().split()))


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
sumDict = dict()
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):

    searchI = 0
    loopSum = 0
    nextIndex = i
    loopCount = 0
    while True:
        nextIndex = ps[nextIndex] - 1
        loopSum += cs[nextIndex]
        loopCount += 1
        if nextIndex == i:
            break

    total = loopSum

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // loopCount
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)
# Original solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    # cycle = 0
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        # cycle += 1
        if pos == i: break
    q,r = divmod(k,l+1)
    if r == 0 and q > 1:
        r = l+1
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)


# Optimized solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    cycle = 0
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        cycle += 1
        if pos == i: break
    q,r = divmod(k,cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)
# Original solution
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        rl.append(tc)
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        s.add(tc)
print((max(s)))

# Optimized solution
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
ans=-10**10
for i in range(N):
    idx=P[i]-1
    z=set()
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tc+=C[idx]
        rl.append(tc)
        ans=max(ans,tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        ans=max(ans,tc)
print(ans)
# Original solution


cache = {0: 1, 1: 1, 2: 2}
combo_cache = {}


def prepare_cache():
    val = 1
    for i in range(1, 10000):
        val *= i
        cache[i] = val

def permutation(n):
    if n in cache:
        return cache[n]

    ret = n
    for i in range(n-1, 0, -1):
        if i in cache:
            ret *= cache[i]
            cache[n] = ret
            return ret

        ret *= i
    return ret


def combo(n, r):
    key = str(n) + "-" + str(r)
    if key in combo_cache:
        return combo_cache[key]

    x = permutation(n)
    y = permutation(n-r)
    z = permutation(r)
    combo_cache[key] = int(x // (y * z))
    return combo_cache[key]


count = int(eval(input()))
li = list(map(int, input().split()))
#
# data = open("input.txt", "r")
# l = data.read()
# li = list(map(int, l.split(" ")))

prepare_cache()

sli = sorted(li)

pair_a = 0
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

for j in range(0, len(sli) - 1):
    val = combo(i, sli[j])
    # print(str(sli[i]) + ", " + str(sli[j]) + ", " + str(val))
    if val > current_max:
        current_max = val
        pair_a = i
        pair_b = sli[j]

print((str(pair_a) + " " + str(pair_b)))


# Optimized solution
count = int(eval(input()))
li = list(map(int, input().split()))

sli = sorted(li)

pair_a = sli[len(sli) - 1]
pair_b = 0
current_max = 0

i = sli[len(sli) - 1]

diff = 10**9
for j in range(0, len(sli) - 1):
    h = pair_a / 2
    if abs(h - sli[j]) < diff:
        diff = abs(h - sli[j])
        pair_b = sli[j]

print((str(pair_a) + " " + str(pair_b)))
# Original solution
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(eval(input()))
a = [int(x) for x in input().split()]

x = max(a)
maxc = 0
maxy = 0
for y in sorted(a):
    if x == y or y < x // 2:
        continue
    c = comb(x, y)
    if maxc < c:
        maxc = c
        maxy = y

print((str(x) + ' ' + str(maxy)))


# Optimized solution
import math

n = int(eval(input()))
a = [int(x) for x in input().split()]
a.sort()
x = max(a)
a.remove(x)
maxi = 0
mind = x
for i in range(len(a)):
    d = abs((x+1) // 2 - a[i])
    if d < mind:
        maxi = i
        mind = d
print((str(x) + ' ' + str(a[maxi])))
# Original solution
s = input().strip()
t = input().strip()

for i in range(len(s)):
    if s[i] != t[i]:
        s = s.translate(str.maketrans({s[i]:t[i], t[i]:s[i]}))

if s == t:
    print("Yes")
else:
    print("No")

# Optimized solution
s = input().strip()
t = input().strip()

scount = []
tcount = []

for x in [chr(i) for i in range(97,97+26)]:
    scount.append(s.count(x))
    tcount.append(t.count(x))

if sorted(scount) == sorted(tcount):
    print("Yes")
else:
    print("No")
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(eval(input()))
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))
def LI2(): return [int(eval(input())) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print(('\n'.join(x)))
def printni(x): print(('\n'.join(list(map(str,x)))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

s=input().rstrip()
t=input().rstrip()
u=Counter(s)
v=Counter(t)
for i in range(len(s)):
    if u[s[i]]!=v[t[i]]:
        print("No")
        #print(i)
        sys.exit()
print("Yes")

# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(eval(input()))
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))
def LI2(): return [int(eval(input())) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print(('\n'.join(x)))
def printni(x): print(('\n'.join(list(map(str,x)))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()


alphasm=[chr(i) for i in range(97, 97+26)]
s=input().rstrip()
t=input().rstrip()
u=Counter(list(s))
v=Counter(list(t))
a,b=[],[]
for i in alphasm:
    a.append(u[i])
    b.append(v[i])
a.sort()
b.sort()
if a==b:
    print("Yes")
else:
    print("No")
# Original solution
S = input()
T = input()

CS = [S.count(s) for s in S]
TS = [T.count(t) for t in T]

if False in [CS[i] == TS[i] for i in range(len(CS))]:
	print('No')
else:
	print('Yes')


# Optimized solution
S = input()
T = input()

CS = {}
for s in S:
	if s not in CS:
		CS[s] = 1
	else:
		CS[s] += 1
TS = {}
for t in T:
	if t not in TS:
		TS[t] = 1
	else:
		TS[t] += 1

if False in [CS[S[i]] == TS[T[i]] for i in range(len(T))]:
	print('No')
else:
	print('Yes')
# Original solution
#!/usr/bin/env python3
S = input().strip()
T = input().strip()

for i in range(len(S)):
    S = S.translate(str.maketrans({S[i]: T[i], T[i]: S[i]}))

print(('Yes' if S == T else 'No'))

# Optimized solution
#!/usr/bin/env python3
S = input().strip()
T = input().strip()

trans = dict()
ans = True
for s, t in zip(S, T):
    if trans.get(s, t) != t:
        ans = False
        break
    trans[s] = t

# print(trans)
print(('Yes' if ans and len(set(trans.values())) == len(trans) else 'No'))
# Original solution
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A = list(iss())
    B = list(iss())
    atob = {}
    btoa = {}
    for n in range(ord('a'), ord('z') + 1):
        atob[chr(n)] = 0
        btoa[chr(n)] = 0

    for ab in zip(A, B):
        a, b = ab
        if atob[a] == 0 and btoa[b] == 0:
            atob[a] = b
            btoa[b] = a
        elif atob[a] != b or btoa[b] != a:
            print('No')
            exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(iss())
    T = list(iss())
    StoT = {}
    TtoS = {}
    for n in range(ord('a'), ord('z') + 1):
        StoT[chr(n)] = 0
        TtoS[chr(n)] = 0

    for st in zip(S, T):
        s, t = st
        if StoT[s] == 0 and TtoS[t] == 0:
            StoT[s] = t
            TtoS[t] = s
        elif StoT[s] != t or TtoS[t] != s:
            print('No')
            exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()
# Original solution
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(iss())
    T = list(iss())
    StoT = {}
    TtoS = {}
    for n in range(ord('a'), ord('z') + 1):
        StoT[chr(n)] = 0
        TtoS[chr(n)] = 0

    for st in zip(S, T):
        s, t = st
        if StoT[s] == 0 and TtoS[t] == 0:
            StoT[s] = t
            TtoS[t] = s
        elif StoT[s] != t or TtoS[t] != s:
            print('No')
            exit()
    else:
        print('Yes')


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import os
import math
import bisect
import collections
import itertools

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = collections.Counter(iss())
    T = collections.Counter(iss())

    if sorted(S.values()) == sorted(T.values()):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()
# Original solution
A = {chr(i):0 for i in range(97,123)}
S = input().strip()
T = input().strip()
N = len(S)
G = {}
for i in range(N):
    a = S[i]
    if a not in G:
        G[a]=[]
    b = T[i]
    if b not in G[a]:
        G[a].append(b)
flag = 0
cnt = 0
for a in G:
    cnt += 1
    if len(G[a])>1:
        flag = 1
        break
    if len(G[a])==0 and cnt==26:
        break
    b = G[a][0]
    if a!=b:
        cnt += 1
    if A[b]==0:
        A[b] += 1
    else:
        flag = 1
        break
if flag==1:
    print("No")
else:
    print("Yes")

# Optimized solution
S = input().strip()
T = input().strip()
N = len(S)
C = {}
D = {}
flag = 0
for i in range(N):
    if S[i] not in C:
        C[S[i]] = T[i]
    elif C[S[i]]!=T[i]:
        flag = 1
        break
    if T[i] not in D:
        D[T[i]] = S[i]
    elif D[T[i]] != S[i]:
        flag = 1
        break
if flag==0:
    print("Yes")
else:
    print("No")
# Original solution
s,t=[sorted(x.count(i)for i in x) for x in open(0)]
print(('YNeos'[s!=t::2]))

# Optimized solution
s,t=[sorted(t.count(i)for i in set(t))for t in open(0)]
print(('YNeos'[s!=t::2]))
# Original solution
from collections import defaultdict
S, T = [x.strip() for x in open(0).read().split()]

ds, dt = defaultdict(str), defaultdict(str)
ans = 'Yes'
for s, t in zip(S, T):
    if not ds[s] or ds[s] == t:
        ds[s] = t
    else:
        ans = 'No'
        break
    if not dt[t] or dt[t] == s:
        dt[t] = s
    else:
        ans = 'No'
        break
print(ans)

# Optimized solution
S, T = input().strip(), input().strip()
ds, dt = {}, {}

for s, t in zip(S, T):
    if s not in ds or ds[s] == t:
        ds[s] = t
    else:
        print('No')
        exit()
    if t not in dt or dt[t] == s:
        dt[t] = s
    else:
        print('No')
        exit()
print('Yes')
# Original solution
sS = input().rstrip()
sT = input().rstrip()




def fConv2B(sA):
    iL = len(sA)
    dA = {}
    for s in "abcdefghijklmnopqrstuvwxyz":
        dA[s] = 0
    iCounter = 1
    for i in range(iL):
        s = sA[i]
        if s in dA:
            if dA[sA[i]] == 0:
                dA[sA[i]] = iCounter
                iCounter += 1
        if  iCounter  == 27 :
            break

    aR = [0]*iL
    for i in range(iL):
        aR[i] = dA[sA[i]]
#   print(aR)
    return aR



if fConv2B(sS) == fConv2B(sT) :
    print("Yes")
else:
    print("No")


# Optimized solution
sS = input().rstrip()
sT = input().rstrip()

aS = [0] * 26
aT = [0] * 26
sABC = "abcdefghijklmnopqrstuvwxyz"
for i in range(26):
    aS[i]=sS.count(sABC[i])
    aT[i]=sT.count(sABC[i])
aS.sort()
aT.sort()
if aS == aT:
    print ("Yes")
else:
    print ("No")
# Original solution
from math import ceil
N = int(eval(input()))
A, B = [], []
for _ in range(N):
    ai, bi = list(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)

# Optimized solution
from math import ceil
N = int(eval(input()))
A, B = [], []
for _ in range(N):
    ai, bi = list(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)
# Original solution
n=int(eval(input()))
a=[list(map(int, input().split())) for i in range(n)]
a=a[::-1]
count=0
for i in range(n):
    b=a[i][0]+count
    if b%a[i][1]!=0:
        count+=a[i][1]-b%a[i][1]
print(count)

# Optimized solution
n=int(eval(input()))
a=[list(map(int, input().split())) for i in range(n)]
c=0
for i,j in a[::-1]:
    if (c+i)%j!=0:
        c+=j-(c+i)%j
print(c)
# Original solution
# AGC009A - Multiple Array
# greedy algorithm
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    A = tuple(tuple(map(int, input().split())) for _ in range(n))
    ans = 0
    for i, j in A[::-1]:  # # decide from the last one
        ans += -(i + ans) % j
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# AGC009A - Multiple Array
def main():
    N, *AB = list(map(int, open(0).read().split()))
    ans = 0
    for i, j in zip(*[iter(AB[::-1])] * 2):  # decide from the last one greedily
        ans += -(j + ans) % i
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
N = int(eval(input()))
A = [None] * N
B = [None] * N
for i in range(N):
  A[i],B[i] = list(map(int, input().split()))
  
ans = 0
for i in range(N):
  p = A[N-1-i] % B[N-1-i]
  if p != 0:
    for j in range(N-i):
      A[j] += B[N-1-i] - p
    ans += B[N-1-i] - p
print(ans)

# Optimized solution
N = int(eval(input()))
A = [None] * N
B = [None] * N
for i in range(N):
  A[i],B[i] = list(map(int, input().split()))
  
ans = 0
for i in range(N):
  p = (A[N-1-i] + ans) % B[N-1-i]
  ans += (B[N-1-i] - p) % B[N-1-i]
print(ans)
# Original solution
n = int(eval(input()))
a_list = []
b_list = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
a_list = list(reversed(a_list))
b_list = list(reversed(b_list))
ans = 0
for i in range(n):
    a = a_list[i]
    b = b_list[i]
    a += ans
    while (a % b != 0):
        a += 1
        ans += 1
print(ans)

# Optimized solution
n = int(eval(input()))
a_list = []
b_list = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
a_list = list(reversed(a_list))
b_list = list(reversed(b_list))
ans = 0
for i in range(n):
    a = a_list[i]
    b = b_list[i]
    a += ans
    if (a % b) != 0:
        ans += b - (a % b)
print(ans)
# Original solution
#!/usr/bin/env python3
(n, ), *s = [[*list(map(int, i.split()))] for i in open(0)]
a, b = list(zip(*s))
c = 0
for i in reversed(list(range(n))):
    q = (a[i] + c) % b[i]
    c += b[i] - q if q > 0 else 0
print(c)


# Optimized solution
#!/usr/bin/env python3
(n, ), *s = [[*list(map(int, i.split()))] for i in open(0)]
c = 0
for a, b in reversed(s):
    q = (a + c) % b
    c += b * (q > 0) - q
print(c)
# Original solution
list_ab = []
n = int(eval(input()))
for i in range(n):
    list_ab.append(list(map(int, input().split())))

j = n - 1
count = 0
while j >= 0:
    if list_ab[j][0] % list_ab[j][1] == 0:
        j -= 1
    else:
        ad = list_ab[j][1] * (list_ab[j][0] // list_ab[j][1] + 1) - list_ab[j][0]
        count += ad
        for i in range(j+1):
            list_ab[i][0] += ad
        j -= 1
print(count)


# Optimized solution
list_ab = []
n = int(eval(input()))
for i in range(n):
    list_ab.append(list(map(int, input().split())))

j = n - 1
ad = 0
while j >= 0:
    list_ab[j][0] += ad
    if list_ab[j][0] % list_ab[j][1] == 0:
        j -= 1
    else:
        ad += list_ab[j][1] * (list_ab[j][0] // list_ab[j][1] + 1) - list_ab[j][0]
        j -= 1
print(ad)
# Original solution
import math
n = int(eval(input()))

a = []
b = []

for i in range(n):
  c, d= list(map(int, input().split()))
  a.append(c)
  b.append(d)

a.reverse()
b.reverse()

tot = 0
for i in range(n):
  if (a[i]+tot)%b[i] == 0:
    continue
  x = b[i] - (a[i]+tot)%b[i]
  tot += x
print (tot)

# Optimized solution
n = int(eval(input()))
a = []
b = []
for i in range(n):
  c, d= list(map(int, input().split()))
  a.append(c)
  b.append(d)
a.reverse()
b.reverse()
tot = 0
for i in range(n):
  if (a[i]+tot)%b[i] == 0: continue
  x = b[i] - (a[i]+tot)%b[i]
  tot += x
print (tot)
# Original solution
n = int(eval(input()))
a, b = [0]*n,[0]*n
count = 0
for i in range(n):
    a[i],b[i] = list(map(int,input().split()))

while(n > 0):
    if((a[n-1]+count)%b[n-1] == 0):
        n -= 1
    else:
        count += 1

print(count)

# Optimized solution
n = int(eval(input()))
a, b = [0]*n,[0]*n
count = 0
for i in range(n):
    a[i],b[i] = list(map(int,input().split()))

while(n > 0):
    n -= 1
    count += (b[n] if (a[n]+count)%b[n]!=0 else 0)-(a[n]+count)%b[n]

print(count)
# Original solution
N = int(eval(input()))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))

cnt = 0
AB.reverse()
for el in AB:
    A, B = el
    A += cnt
    while A % B != 0:
        A += 1
        cnt += 1
print(cnt)

# Optimized solution
N = int(eval(input()))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))

cnt = 0
AB.reverse()
for el in AB:
    A, B = el
    A += cnt
    if A % B != 0:
        cnt += (B - A % B)
print(cnt)