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 si-th day and works every di day. So, he works on days si, si + di, si + 2di, ....

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 si and di (1 ≤ si, di ≤ 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.
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;

/**
 * Created by ayan.ghatak on 15/11/17.
 */
public class TaskA {
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    static class Pair<X extends Comparable<X>, Y extends Comparable<Y>> implements Comparable<Pair<X, Y>> {
        private X first;
        private Y second;

        public Pair(X first, Y second) {
            this.first = first;
            this.second = second;
        }


        public int compareTo(Pair<X, Y> o) {
            if (first.compareTo(o.first) == 0) return second.compareTo(o.second);
            else return first.compareTo(o.first);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair<X, Y> pair = (Pair<X, Y>) o;

            if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
            return second != null ? second.equals(pair.second) : pair.second == null;
        }

        @Override
        public int hashCode() {
            int result = first != null ? first.hashCode() : 0;
            result = 31 * result + (second != null ? second.hashCode() : 0);
            return result;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "first=" + first +
                    ", second=" + second +
                    '}';
        }
    }


    private static int n;
    private static int[] s;
    private static int[] d;
    private static int[] hashedIndices;
    private static ArrayList<Pair<Integer, Integer>> arr = new ArrayList<Pair<Integer, Integer>>();

    private static void scan() throws IOException {
        Reader reader = new Reader();
        n = reader.nextInt();
        s = new int[n];
        d = new int[n];
        hashedIndices = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = reader.nextInt();
            d[i] = reader.nextInt();
        }
    }

    private static void out() {
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                arr.add(new Pair<Integer, Integer>(s[i] + j*d[i], i));
//            }
//        }
//        Collections.sort(arr);
//        Pair<Integer, Integer> prev= new Pair<Integer, Integer>(-1, -1);
//        int count =0 ;
//        for( Pair<Integer, Integer> p : arr){
//            if(hashedIndices[p.second] == 0 && p.first.compareTo(prev.first)!=0)
//            {
//                count = count + 1;
//                hashedIndices[p.second] = 1;
//                prev = p;
//            }
//            if(count == n){
//                System.out.println(p.first);
//                return;
//            }
//        }

        for (int i = 1; i < n; i++) {
            while (s[i] <= s[i - 1]) s[i] += d[i];
        }
        System.out.println(s[n - 1]);
    }

    public static void main(String[] args){
        try {
            scan();
            out();
        } catch (IOException e){
            System.out.println("Exception");
        }
    }
}
