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

import sys
input = sys.stdin.readline
n,m= map(int,input().split())
A =[list(map(str,input().split())) for _ in range(m)]
B = []
C = []
ans = 0
pna = 0
for i in range(m):
    if A[i][1]=="AC":
        if A[i][0] not in B :
            B.append(A[i][0])
            ans += 1
            pna += C.count(A[i][0])
    if A[i][1]=="WA"  :
        C.append(A[i][0])
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    t = 0
    ls = [0] * 70
    for v in a:
        tt = bin(v)
        for i in range(len(tt)-2):
            ls[i] += int(tt[-i-1])
    for v in a:
        tt = bin(v)
        for i in range(len(tt)-2):
            if tt[-i-1] == "1":
                t += 2 ** i * (n - ls[i])
                t %= mod
    print(t)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    ls = [0] * 65
    for v in a:
        tt = bin(v)
        for i in range(len(tt)-2):
            ls[i] += int(tt[-i-1])
    t = 0
    for i in range(len(ls)):
        t += 2 ** i * (n - ls[i]) * ls[i]
        t %= mod
    print(t)


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

def main():
    def prime_pair(n):
        pairs = {}
        tmp = n
        for i in range(2, n):
            if i * i > n:
                break
            if tmp % i != 0:
                continue
            ex = 0
            while tmp % i == 0:
                ex += 1
                tmp /= i
            pairs[i] = ex
        if tmp != 1:
            pairs[int(tmp)] = 1
        return pairs

    N = int(input())
    a_list = list(map(int, input().split()))
    a_pp_list = []
    MOD = 10**9 + 7

    a_lcm = {}
    key_set = set()
    for a in a_list:
        a_pp = prime_pair(a)
        a_pp_list.append(a_pp)
        for k in a_pp.keys():
            if k not in key_set:
                key_set.add(k)
                a_lcm[k] = a_pp[k]
            else:
                a_lcm[k] = max(a_lcm[k], a_pp[k])

    a_l = 1
    for k in a_lcm.keys():
        a_l *= k ** a_lcm[k]

    res = 0
    for a in a_list:
        res = (res + a_l // a) % MOD
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###


from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

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

import sys
x=input()
tmp=x.split("ST")
tmp=''.join(tmp)
a=len(tmp)
for i in range(100000):
    tmp=tmp.split("ST")
    tmp=''.join(tmp)
    if len(tmp)==a:
        print(len(tmp))
        break
    elif len(tmp)==0:
        print(0)
        break
    else:
        a=len(tmp)


### FIXED CODE ###

if __name__ == '__main__':
    x = list(input())
    sl = []
    ans = 0
    for i in x:
        if i == "S":
            sl.append(1)
        else:
            if len(sl) != 0:
                ans += sl.pop()

    print(len(x) - ans * 2)
### BUGGY CODE ###

from collections import deque
n = int(input())
d = deque()
for _ in range(n):
    x = input().split()
    if x[0][0] == 'i':
        d.appendleft(int(x[1]))
    elif x[0] == 'delete':
        try:
            d.remove(int(x[1]))
        except ValueError:
            pass
    elif x[0][6] == 'F':
        d.popleft()
    else:
        d.pop()
print(*d)


### FIXED CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input()
    if b[0]=='i':a.appendleft(b[7:])
    elif b[6]==' ':
        try:a.remove(b[7:])
        except:pass
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
print(*a)
### BUGGY CODE ###

n,m=map(int,input().split(' '))
war=[tuple(map(int,input().split(' '))) for _ in range(m)]
war.sort(key=lambda x:x[1])
bridge=[0]*n
for w in war:
    if not 1 in set(bridge[w[0]:w[1]]):
        bridge[w[1]-1]=1
print(sum(bridge))

### FIXED CODE ###

n,m=map(int,input().split(' '))
war=[tuple(map(int,input().split(' '))) for _ in range(m)]
war.sort(key=lambda x:x[1])
bridge=[0]*n
flag=0
for w in war:
    if not w[0]<=flag<w[1]:
        flag=w[1]-1
        bridge[flag]=1
print(sum(bridge))
### BUGGY CODE ###

N=raw_input()
b=[]
P=raw_input().split()
for i in P:
    b.append(i)
    b=b[::-1]
print " ".join(b)

### FIXED CODE ###

N=int(raw_input())
P=raw_input().split()
b=P[-1::-2]+P[N%2::2]
print " ".join(b)
### BUGGY CODE ###

A,B = map(int,input().split())
T = max(len(format(A,'b')),len(format(B,'b')))
As = format(A,'b').zfill(T)    
Bs = format(B,'b').zfill(T)

GT = format(A,'b').zfill(T)

for j in range(A+1,B+1):
    Bs = format(j,'b').zfill(T)
    s =''
    for i in range(T):
        if GT[i] != Bs[i]:
            s += '1'
        else:
            s += '0' 
    GT = s
else:print(int(GT,2))

### FIXED CODE ###

def xor_sum(n):
    m1 = (n+1)//4
    m2 = (n+1)%4
    if m2 == 0:return 0
    else:
        ret = 0
        for i in range(m1*4,m1*4+m2):ret ^= i
        else: return ret

a,b = map(int, input().split())
if a==b:print(a)
else:
    ans = xor_sum(a-1) ^ xor_sum(b)
    print(ans)
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]

    for i in range(len(nums)):
        tmp = nums[i]
        nums[i] = 0
    
        print(max(nums))
        
        nums[i] = tmp


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]
    a = deepcopy(nums)
    a.sort(reverse=True)

    for i in range(len(nums)):
        if a[0] == nums[i]:
            print(a[1])
        else:
            print(a[0])


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

import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
a = list(map(int,input().split()))
from fractions import gcd
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , a[i])
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
print(ans)

### FIXED CODE ###

from fractions import gcd
import copy

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2 ** (N-1).bit_length()
        self.func = copy.deepcopy(func)
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]

    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)

    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])

    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

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

def f(x,y):
    if x * y == 0:
        return x + y
    else:
        return gcd(x,y)

seg = SegmentTree(N + 1, f, 0)
for i in range(N):
    seg.assign(i , A[i])
seg.build()

ans = 1
for i in range(N):
    ans = max(ans , f(seg.query(0 , i) , seg.query(i + 1 , N)))
print(ans)
### BUGGY CODE ###

def g(field,x,y,h,w):
     cnt = 1
     while True:
          for i in range(0,cnt+1):
               j = cnt - i
               search = [[x+i,y+j],[x-i,y+j],[x+i,y-j],[x-i,y-j]]
               #print(search,cnt)
               for p in search:
                    if (1<=p[0]) and (p[0]<=w) and (1<=p[1]) and (p[1]<=h):
                         if field[p[1]][p[0]] == "#":
                              return cnt
          cnt += 1


def f():
     h,w = map(int,input().split())
     field = [["!"]*w ]
     for i in range(h):
          field.append(["!"]+list(input())+["!"])
     field.append(["!"]*w)
     ans = [["#"]*w for i in range(h)]
     for i in range(1,h+1):
          for j in range(1,w+1):
               if field[i][j] == "#":
                    ans[i-1][j-1] = 0
               elif field[i][j] == ".":
                    ans[i-1][j-1] = g(field,j,i,h,w)
     a = -1
     for i in range(h):
          #print(ans[i])
          a = max(a,max(ans[i]))
     print(a)
     return
f()

### FIXED CODE ###

def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()
### BUGGY CODE ###

import sys
from math import sqrt

testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[INF] * N for _ in range(1 << N)]
    dp[(1 << N) - 1][0] = 0
    for state in reversed(range(1 << N)):
        for v in range(N):
            if not dp[state][v]:
                continue
            for u in range(N):
                if not (state >> u & 1):
                    dp[state][v] = min(dp[state][v], dp[state | 1 << u][u] + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    print('OK' if min(dp[0]) <= box else 'NA')

### FIXED CODE ###

import sys
from math import sqrt


def rec(state, v):
    if state == (1 << N) - 1:
        return cakes[v]
    if dp[state][v] != -1:
        return dp[state][v]

    ret = INF
    for u in range(N):
        if state == 0:
            ret = min(ret, rec(1 << u, u) + cakes[u])
        elif not (state >> u & 1):
            ret = min(ret, rec(state | 1 << u, u) + sqrt(pow(cakes[u] + cakes[v], 2) - pow(cakes[u] - cakes[v], 2)))
    dp[state][v] = ret
    return ret


testcases = [[int(x) for x in line.split()] for line in sys.stdin.readlines()]

for testcase in testcases:
    box, *cakes = testcase
    N = len(cakes)
    INF = box + 1
    dp = [[-1] * N for _ in range(1 << N)]
    print('OK' if rec(0, 0) <= box else 'NA')
### BUGGY CODE ###

import itertools
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for _ in range(H)]
Q = int(input())
LR = [[int(_) for _ in input().split()] for _ in range(Q)]

G = [[0, 0]] * (H * W + 1)

for i, j in itertools.product(range(H), range(W)):
    G[A[i][j]] = [i, j]

for l, r in LR:
    ans = 0
    x1, y1 = G[l]
    for i in range(l, r, D):
        x0, y0 = G[i]
        x1, y1 = G[i + D]
        ans += abs(x1 - x0) + abs(y1 - y0)
    print(ans)


### FIXED CODE ###

import itertools
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for _ in range(H)]
Q = int(input())
LR = [[int(_) for _ in input().split()] for _ in range(Q)]

G = [[0, 0]] * (H * W + 1)

for i, j in itertools.product(range(H), range(W)):
    G[A[i][j]] = [i, j]

S = [0] * (H * W + 1)

for i in range(D + 1, H * W + 1):
    x1, y1 = G[i]
    x2, y2 = G[i - D]
    S[i] += S[i - D] + abs(x1 - x2) + abs(y1 - y2)

for l, r in LR:
    print(S[r] - S[l])
### BUGGY CODE ###

s=list(input())
q=int(input())
info=[]
rev=[] #i回までに何回反転があるか
num=0
for i in range(q):
    info.append(list(input().split()))
moji=0 #文字の追加数
for i in range(q):
    if info[i][0]=="1":
        num+=1
    else:
        if info[i][1]=="2":
            rev.append([info[i][2],2,num]) #末尾
        else:
            rev.append([info[i][2],1,num])
        moji+=1
if num%2==1:
    s.reverse()
#print(rev)
#print(num)
for i in range(moji):
    now=rev[i][1]
    if (num-rev[i][2])%2==1: #これが奇数だと２なら先頭になる
        if now==2:
            now=1
        else:
            now=2
    if now==2:
        s.append(rev[i][0])
    else:
        s.insert(0,rev[i][0])
print("".join(s))

### FIXED CODE ###

from collections import deque
ss=deque()
s=list(input())
l=len(s)
for i in range(l):
    ss.append(s[i])
q=int(input())
info=[]
rev=[] #i回までに何回反転があるか
num=0
for i in range(q):
    info.append(list(input().split()))
moji=0 #文字の追加数
for i in range(q):
    if info[i][0]=="1":
        num+=1
    else:
        if info[i][1]=="2":
            rev.append([info[i][2],2,num]) #末尾
        else:
            rev.append([info[i][2],1,num])
        moji+=1
if num%2==1:
    ss.reverse()
#print(rev)
#print(num)
for i in range(moji):
    now=rev[i][1]
    if (num-rev[i][2])%2==1: #これが奇数だと２なら先頭になる
        #print("change")
        if rev[i][1]==2:
            rev[i][1]=1
        else:
            rev[i][1]=2
    if rev[i][1]==2:
        ss.append(rev[i][0])
    else:
        ss.appendleft(rev[i][0])
print("".join(ss))
#print(rev)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
for i in range(N):
  a*=A[i]
print(a if a<=10**(18) else -1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
k=0
if 0 in A:
  print(0)
else:
  for i in range(N):
    a*=A[i]
    if a>10**(18):
      k=1
      break
  if k==1:
    print(-1)
  else:
    print(a)
### BUGGY CODE ###

k,s = map (int ,input ().split ())
x = 0
y = 0
z = 0
p = 0
while x <= k:
  while y <= k:
    while z <= k:
      if x+y+z == s:
        p += 1
      z += 1
    y += 1
    z = 0
  x += 1
  y,z = 0,0
print (p)

### FIXED CODE ###

k,s = map (int ,input ().split ())
x = 0
y = 0
p = 0
while x <= k:
  while y <= k:
    if x+y > s:
      break
    z = s-(x+y)
    if 0 <= z <= k:
      p += 1
    y += 1
  x += 1
  y = 0
print (p)
### BUGGY CODE ###

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

def otosidama(N,Y):
    for y in range(N+1,-1,-1):
        if y*10000 > Y:
            continue
        for i in range(N+1-y,-1,-1):
            if i*5000 > Y-y*10000:
                continue
            for h in range(N+1-y-i,-1,-1):
                if y*10000 + i*5000 + h*1000 == Y and y + i + h == N:
                    return y,i,h
    
    return -1,-1,-1

if Y > N*10000:
    print(-1,-1,-1)
else:
    y,i,h = otosidama(N,Y)
    print(y,i,h)

### FIXED CODE ###

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

def otosidama(N,Y):
    for y in range(N+1,-1,-1):
        if y*10000 > Y:
            continue
        for i in range(N+1-y):
            if (N-y-i)*1000 > Y-y*10000:
                break
            else:
                if y*10000 + i*5000 + (N-y-i)*1000 == Y:
                    return y,i,N-y-i
    
    return -1,-1,-1

if Y > N*10000:
    print(-1,-1,-1)
else:
    y,i,h = otosidama(N,Y)
    print(y,i,h)
### BUGGY CODE ###

import sys
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-2, step_dict) + step2patterns(num_step-1, step_dict)
        step_dict[num_step] = ret
        return ret


sys.setrecursionlimit(100000)
num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


### FIXED CODE ###

def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)
### BUGGY CODE ###

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

count = 0
while True:
    select = 0
    min_val = AB_array[0][0]
    for i in range(1,len(AB_array)):
        if AB_array[i][0] < min_val:
            min_val = AB_array[i][0]
            select = i
    if M <= AB_array[select][1]:
        count += AB_array[select][0] * M
        break
    else:
        M -= AB_array[select][1]
        count += AB_array[select][0] * AB_array[select][1]
        AB_array.pop(select)

print(count)


### FIXED CODE ###

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

AB_array_s = sorted(AB_array, key=lambda x: x[0])

count = 0
for i in range(len(AB_array_s)):
    A,B = AB_array_s[i]
    if M <= B:
        count += A * M
        break
    else:
        M -= B
        count += A * B

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

N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  if C>=min(list1):
    list1+=[C]*B
    list1.sort(reverse=True)
    list1=list1[:N]
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

import math
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  cnt = 0
  for i in range(N):
    tmp = a[i] - x//f[i]
    cnt += max(tmp, 0)
  else:
    if cnt <= K:
      return True
    else:
      return False

# 二分探索 #
def nibutan(): # MAX(A*F) ans
    left = -1
    ans = num
    while left+1 != ans:
        middle = (left+ans)//2
        if judge(middle):
            ans = middle
        else:
            left = middle
    return ans

N, K = IL()
a = IL()
f = IL()
a.sort()
f.sort(reverse=True)
num = 0
for i in range(N):
  num = max(num, a[i]*f[i])

print(nibutan())


### FIXED CODE ###

import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def judge(x):
  cnt = 0
  for i in range(N):
    tmp = a[i] - x//f[i]
    cnt += max(tmp, 0)
  else:
    if cnt <= K:
      return True
    else:
      return False

# 二分探索 #
def nibutan(): # MAX(A*F) ans
    left = -1
    ans = num
    while left+1 != ans:
        middle = (left+ans)//2
        if judge(middle):
            ans = middle
        else:
            left = middle
    return ans

N, K = IL()
a = IL()
f = IL()
a.sort()
f.sort(reverse=True)
num = 0
for i in range(N):
  num = max(num, a[i]*f[i])

print(nibutan())
### BUGGY CODE ###

import numpy as np

n = int(input())
num = np.array([list(map(int, input().split())) for i in range(n)])

ans = 0
for i in range(n-1, -1, -1):
    a, b = num[i][0], num[i][1]
    if a % b != 0:
        cnt = b - a % b
        num[:i+1] += [cnt, 0]
        ans += cnt

print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(n-1, -1, -1):
    a, b = num[i][0], num[i][1]
    a += ans
    if a % b != 0:
        res = b - a % b
        ans += res

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

from heapq import *
def main():
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    inf=float('inf')
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append([j,d_temp])
            g[j].append([i,d_temp])
    d=[10**10]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append([j,i])
    heapify(h)
    while h:
        i,j=heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heappush(h,[l+i,k])
    print(d[1])
main()

### FIXED CODE ###

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    xs,ys,xt,yt=map(int,input().split())
    n=int(input())
    xyr=[[xs,ys,0],[xt,yt,0]]+[list(map(int,input().split())) for _ in [0]*n]
    g=[[] for _ in [0]*(n+2)]
    for i in range(n+1):
        x1,y1,r1=xyr[i]
        for j in range(i+1,n+2):
            x2,y2,r2=xyr[j]
            d_temp=max(0,((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2)
            g[i].append((j,d_temp))
            g[j].append((i,d_temp))
    d=[0]*(n+2)
    visit=[False]*(n+2)
    visit[0]=True
    h=[]
    for i,j in g[0]:
        h.append((j,i))
    heapq.heapify(h)
    while h:
        i,j=heapq.heappop(h)
        if visit[j]==True:
            continue
        visit[j]=True
        d[j]=i
        for k,l in g[j]:
            if visit[k]==False:
                heapq.heappush(h,(l+i,k))
    print(d[1])
main()