It seems that Borya is seriously sick. He is going visit n doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in the prescribed order (i.e. Borya should first visit doctor 1, then doctor 2, then doctor 3 and so on). Borya will get the information about his health from the last doctor.

Doctors have a strange working schedule. The doctor i goes to work on the s_{i}-th day and works every d_{i} day. So, he works on days s_{i}, s_{i} + d_{i}, s_{i} + 2d_{i}, ....

The doctor's appointment takes quite a long time, so Borya can not see more than one doctor per day. What is the minimum time he needs to visit all doctors?


-----Input-----

First line contains an integer n — number of doctors (1 ≤ n ≤ 1000). 

Next n lines contain two numbers s_{i} and d_{i} (1 ≤ s_{i}, d_{i} ≤ 1000).


-----Output-----

Output a single integer — the minimum day at which Borya can visit the last doctor.


-----Examples-----
Input
3
2 2
1 2
2 2

Output
4

Input
2
10 1
6 5

Output
11



-----Note-----

In the first sample case, Borya can visit all doctors on days 2, 3 and 4.

In the second sample case, Borya can visit all doctors on days 10 and 11.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
ans = 0
for i in range(n):
	s, d = list(map(int, input().split()))
	visit = s
	while visit <= ans:
		visit += d
	ans = visit
print(ans)



n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

cur = 0
for i in data:
    if i[0] > cur:
        cur = i[0]
        continue
    c = cur + 1 - i[0]
    c1 = (c // i[1] + (c % i[1] > 0))
    cur = i[0] + i[1] * c1
print(cur)


import math
n = int(input())
current_day = 0
for i in range(0,n):
    current_day = current_day + 1
    (s,d) = [int(x) for x in input().split(' ')]
    p = max(0, math.ceil((current_day - s) / d))
    current_day = s + p * d

print(current_day);

n = int(input())
s, d = list(map(int, input().split()))
last = s
for i in range(n - 1):
    s, d = list(map(int, input().split()))
    c = max(0, last - s)
    c = (c + d) // d
    new = c * d + s
    if new - d >= last:
        new -= d
    if new <= last:
        new += d
    last = new
print(last)


#!/bin/python
import collections
import random
import sys


n = int(input())
day = 0
for i in range(n):
    s, d = list(map(int, input().split()))
    day = max(day + 1, s)
    if (day - s) % d != 0:
        day += d - (day - s) % d
print(day)


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n = ii()
a = [mi() for i in range(n)]
p = 0
for i in range(n):
    s, d = a[i]
    if s>p:
        p = s
    else:
        q = p - s
        p = s + d*(q//d + 1)
print(p)

import math
import re
import os
import string
import sys


def ria():
    return [int(i) for i in input().split()]


def ri():
    return int(input())


def rfa():
    return [float(i) for i in input().split()]


eps = 1e-9


def is_equal(a, b):
    return abs(a - b) <= eps


def distance(p0, p1):
    return math.sqrt((p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2)


def distance_sqr(p0, p1):
    return (p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2


n = ri()
curD = 1
for i in range(n):
    s, d = ria()
    while s > curD or (curD - s) % d != 0:
        curD += 1
    curD+=1
print(curD-1)


from math import ceil

d = int(input())

a = list()
for k in range(d):
    s, l = input().split()
    a.append((int(s), int(l)))

t = a[0][0]
for i in a[1:]:
    s, l = i

    if s > t:
        t = s
    else:
        n = ceil((t - s + 1) / l)
        t = s + l * n

print(t)


from math import * 
ans=0
for _ in range(int(input())):
  si,di=list(map(int,input().split()))
  if si>=ans:
    ans=si+1
    continue
  n=ans-si
  ans=si+ceil(n/di)*di+1
print(ans-1)


n = int(input())
ans = 0
c = 1
import math
for i in range(n):
    s,d = map(int, input().split())
    p = int(math.ceil(max(0, c - s) / d))
    c = s + p*d + 1
print(c-1)

def main():
    n = int(input())
    t = -1
    for i in range(n):
        si, di = list(map(int, input().split()))
        if t < si:
            t = si
        else:
            t = ((t - si) // di + 1) * di + si

    print(t)


def __starting_point():
    main()

__starting_point()

n = int(input())
actual = 1
for _ in range(n):
    s, d = list(map(int, input().split()))
    if actual <= s:
        actual = s
    elif (actual - s) % d != 0:
        actual += (d - (actual - s) % d)
    actual += 1
print(actual-1)


n = int(input())
ans = 0
for i in range(n):
    s, d = list(map(int, input().split()))
    if ans == 0:
        ans = s
    elif s > ans:
        ans = s
    else:
        ans = d * ((ans - s) // d + 1) + s
print(ans)
    


n = int(input())
c = 0
for i in range(n):
    s, d = map(int, input().split())
    if c < s:
        c = s
    else:
        c = s + ((c - s) // d + 1) * d
print(c)

#python3
#utf-8

doctors_nr = int(input())
doctor_idx___start_day_idx = []
doctor_idx___delta = []
for _ in range(doctors_nr):
    start_day_idx, delta = (int(x) for x in input().split())
    doctor_idx___start_day_idx.append(start_day_idx)
    doctor_idx___delta.append(delta)

doctors_visited_nr = 0
for day_idx in range(1, 3000000):
    curr_start_day_idx = doctor_idx___start_day_idx[doctors_visited_nr]
    curr_delta = doctor_idx___delta[doctors_visited_nr]
    if (day_idx >= curr_start_day_idx) and (day_idx % curr_delta == curr_start_day_idx % curr_delta):
        doctors_visited_nr += 1
        if doctors_visited_nr == doctors_nr:
            print(day_idx)
            quit()


import math

n = int(input())
schedules = []
for _ in range(n):
	schedules.append(tuple(map(int, input().split())))

day = 0
for start, period in schedules:
	lower_bound = (day - start) / period
	if lower_bound.is_integer():
		lower_bound = int(lower_bound + 1)
	else:
		lower_bound = math.ceil(lower_bound)
	lower_bound = max(0, lower_bound)
	
	day = start + period * lower_bound

print(day)

def solve():
    N = int(input())
    a, b = map(int, input().split())
    day = a
    for a, b in ((map(int, input().split())) for _ in [0]*(N-1)):
        if day < a:
            day = a
        else:
            diff = b-((day-a)%b)
            day = day+diff if diff > 0 else day+b

    print(day)


def __starting_point():
    solve()
__starting_point()

import math
n=int(input())
t=0
for i in range(n):
    t+=1
    s,d=list(map(int,input().split()))
    k=max(math.ceil((t-s)/d),0)
    t=s+d*k
print(t)


def visit(doctors, i, ret):
  s, d = doctors[i]
  t = ret - s
  if t < 0:
    return s
  return ((t+(d-1))//d)*d+s




n = int(input())
doctors = []
for i in range(n):
  s, d = list(map(int, input().split(' ')))
  doctors.append((s,d))


ret = 0
for i in range(n):
  ret = visit(doctors, i, ret+1)

print(ret)

n = int(input())
day = 1

for i in range(n):
  start, extra = list(map(int, input().split()))
  day = max(day, start)

  while (day - start) % extra != 0:
    day += 1
  if i + 1 < n:
    day += 1

print(day)


n=int(input());a=[];
for i in range(n):
    a.append(list(map(int,input().split())))
curr=0
for i in range(n):
    if(curr<a[i][0]):
        curr=a[i][0]
    else:
        curr=a[i][0] + (((curr-a[i][0])//a[i][1])+1)*a[i][1]
print(curr)





def main():
	n = int(input())
	day = 0
	for i in range(n):
		s, d = list(map(int,input().split()))
		if s > day:
			day = s
		else:
			day  = ((day -s)//d +1)*d +s
	print(day)

main()


n = int(input())
day =0

for i in range(n):
  s,d = input().strip().split()
  s = int(s)
  d = int(d)
  if i==0:
    day = s
  else:
    if s > day:
      day =s
    else:
      day = s + (1+(day -s)//d) * d
print(day)

import math

n = int(input())
sd = [tuple(map(int,input().split())) for _ in range(n)]
cd = 1

for i in range(n):
    s = sd[i][0]
    d = sd[i][1]
    if s>=cd:
        cd = s
    else:
        cd=s+math.ceil((cd-s)/d)*d
    cd+=1

cd-=1
print(cd)

n = int(input())
cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if a > cnt:
        cnt = a
    else:
        cnt = cnt - (cnt - a) % b + b
    #print(cnt)
print(cnt)