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.
/**
 * Created by Ahmed on 10/26/2017.
 */
public class App {

    public static void main(String[] args){
        InputReader reader = new InputReader(System.in);

        try {
            int numOfDocs = reader.nextInt();
            int day = reader.nextInt();
            int trash = reader.nextInt();

            for (int i=1; i<numOfDocs; i++){
                int s = reader.nextInt();
                int a = reader.nextInt();

                int j=s;
                int k=1;
                while (j <= day){
                    j= s + (k*a);
                    k++;
                }
                day = j;
            }

            System.out.print(day);

        }catch (Exception e){

        }
    }

}










/**
 * A very fast input reader to read data from any InputStream (System.in in particular).
 * I primarily use this input reader for competitive programming to get an edge on the
 * time required to read input. That being said, this input reader assumes you know what
 * data types you are reading in and will not do any validation of input whatsoever!
 *
 * @author William Fiset, william.alexandre.fiset@gmail.com
 **/

class InputReader {

    private int c, bufferSize, bufIndex, numBytesRead;

    private final byte[] buf;
    private final java.io.InputStream stream;

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final java.io.InputStream DEFAULT_STREAM = System.in;

    private static final byte EOF   = -1; // End Of File (EOF) character
    private static final byte NL    = 10; // '\n' - New Line (NL)
    private static final byte SP    = 32; // ' '  - Space character (SP)
    private static final byte DASH  = 45; // '-'  - Dash character (DASH)
    private static final byte DOT   = 46; // '.'  - Dot character (DOT)

    // The maximum number of accurate decimal digits .nextDoubleFast can read
    private static final int MAX_DECIMAL_PRECISION = 21;

    // A character buffer I reuse when reading string data.
    private static char[] charBuffer = new char[128];

    // Lookup tables used for optimizations
    private static byte[] bytes = new byte[58];
    private static int [] ints  = new int[58];
    private static char[] chars = new char[128];

    static {
        char ch = ' '; int value = 0; byte _byte = 0;
        for (int i = 48; i <  58; i++ ) bytes[i] = _byte++;
        for (int i = 48; i <  58; i++ )  ints[i] = value++;
        for (int i = 32; i < 128; i++ ) chars[i] = ch++;
    }

    // double lookup table, used for optimizations.
    private static final double[][] doubles = {
            { 0.0d,0.00d,0.000d,0.0000d,0.00000d,0.000000d,0.0000000d,0.00000000d,0.000000000d,0.0000000000d,0.00000000000d,0.000000000000d,0.0000000000000d,0.00000000000000d,0.000000000000000d,0.0000000000000000d,0.00000000000000000d,0.000000000000000000d,0.0000000000000000000d,0.00000000000000000000d,0.000000000000000000000d },
            { 0.1d,0.01d,0.001d,0.0001d,0.00001d,0.000001d,0.0000001d,0.00000001d,0.000000001d,0.0000000001d,0.00000000001d,0.000000000001d,0.0000000000001d,0.00000000000001d,0.000000000000001d,0.0000000000000001d,0.00000000000000001d,0.000000000000000001d,0.0000000000000000001d,0.00000000000000000001d,0.000000000000000000001d },
            { 0.2d,0.02d,0.002d,0.0002d,0.00002d,0.000002d,0.0000002d,0.00000002d,0.000000002d,0.0000000002d,0.00000000002d,0.000000000002d,0.0000000000002d,0.00000000000002d,0.000000000000002d,0.0000000000000002d,0.00000000000000002d,0.000000000000000002d,0.0000000000000000002d,0.00000000000000000002d,0.000000000000000000002d },
            { 0.3d,0.03d,0.003d,0.0003d,0.00003d,0.000003d,0.0000003d,0.00000003d,0.000000003d,0.0000000003d,0.00000000003d,0.000000000003d,0.0000000000003d,0.00000000000003d,0.000000000000003d,0.0000000000000003d,0.00000000000000003d,0.000000000000000003d,0.0000000000000000003d,0.00000000000000000003d,0.000000000000000000003d },
            { 0.4d,0.04d,0.004d,0.0004d,0.00004d,0.000004d,0.0000004d,0.00000004d,0.000000004d,0.0000000004d,0.00000000004d,0.000000000004d,0.0000000000004d,0.00000000000004d,0.000000000000004d,0.0000000000000004d,0.00000000000000004d,0.000000000000000004d,0.0000000000000000004d,0.00000000000000000004d,0.000000000000000000004d },
            { 0.5d,0.05d,0.005d,0.0005d,0.00005d,0.000005d,0.0000005d,0.00000005d,0.000000005d,0.0000000005d,0.00000000005d,0.000000000005d,0.0000000000005d,0.00000000000005d,0.000000000000005d,0.0000000000000005d,0.00000000000000005d,0.000000000000000005d,0.0000000000000000005d,0.00000000000000000005d,0.000000000000000000005d },
            { 0.6d,0.06d,0.006d,0.0006d,0.00006d,0.000006d,0.0000006d,0.00000006d,0.000000006d,0.0000000006d,0.00000000006d,0.000000000006d,0.0000000000006d,0.00000000000006d,0.000000000000006d,0.0000000000000006d,0.00000000000000006d,0.000000000000000006d,0.0000000000000000006d,0.00000000000000000006d,0.000000000000000000006d },
            { 0.7d,0.07d,0.007d,0.0007d,0.00007d,0.000007d,0.0000007d,0.00000007d,0.000000007d,0.0000000007d,0.00000000007d,0.000000000007d,0.0000000000007d,0.00000000000007d,0.000000000000007d,0.0000000000000007d,0.00000000000000007d,0.000000000000000007d,0.0000000000000000007d,0.00000000000000000007d,0.000000000000000000007d },
            { 0.8d,0.08d,0.008d,0.0008d,0.00008d,0.000008d,0.0000008d,0.00000008d,0.000000008d,0.0000000008d,0.00000000008d,0.000000000008d,0.0000000000008d,0.00000000000008d,0.000000000000008d,0.0000000000000008d,0.00000000000000008d,0.000000000000000008d,0.0000000000000000008d,0.00000000000000000008d,0.000000000000000000008d },
            { 0.9d,0.09d,0.009d,0.0009d,0.00009d,0.000009d,0.0000009d,0.00000009d,0.000000009d,0.0000000009d,0.00000000009d,0.000000000009d,0.0000000000009d,0.00000000000009d,0.000000000000009d,0.0000000000000009d,0.00000000000000009d,0.000000000000000009d,0.0000000000000000009d,0.00000000000000000009d,0.000000000000000000009d }
    };

    public InputReader () {
        this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
    }

    public InputReader(int bufferSize) {
        this(DEFAULT_STREAM, bufferSize);
    }

    public InputReader(java.io.InputStream stream) {
        this(stream, DEFAULT_BUFFER_SIZE);
    }

    // Designated constructor
    public InputReader (java.io.InputStream stream, int bufferSize) {
        if (stream == null || bufferSize <= 0)
            throw new IllegalArgumentException();
        buf = new byte[bufferSize];
        this.bufferSize = bufferSize;
        this.stream = stream;
    }

    // Reads a single character from the input stream.
    // Returns the byte value of the next character in the buffer.
    // Also throws exception if there is no more data to read
    private byte read() throws java.io.IOException {

        if (numBytesRead == EOF) throw new java.io.IOException();

        if (bufIndex >= numBytesRead) {
            bufIndex = 0;
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF)
                return EOF;
        }

        return buf[bufIndex++];

    }

    // Read values from the input stream until you reach
    // a character with a higher ASCII value than 'token'
    private int readJunk(int token) throws java.io.IOException {

        if (numBytesRead == EOF) return EOF;

        // Seek to the first valid position index
        do {

            while(bufIndex < numBytesRead) {
                if (buf[bufIndex] > token) return 0;
                bufIndex++;
            }

            // reload buffer
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF) return EOF;
            bufIndex = 0;

        } while(true);

    }

    // Reads a single byte from the input stream
    public byte nextByte() throws java.io.IOException {
        return (byte) nextInt();
    }

    // Reads a 32bit signed integer from input stream
    public int nextInt() throws java.io.IOException {

        if (readJunk(DASH-1) == EOF) throw new java.io.IOException();
        int sgn = 1, res = 0;

        c = buf[bufIndex];
        if (c == DASH) { sgn = -1; bufIndex++; }

        do {

            while(bufIndex < numBytesRead) {
                if (buf[bufIndex] > SP) {
                    res = (res<<3)+(res<<1);
                    res += ints[buf[bufIndex++]];
                } else {
                    bufIndex++;
                    return res*sgn;
                }
            }

            // Reload buffer
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF) return res*sgn;
            bufIndex = 0;

        } while(true);

    }

    // Reads a 64bit signed integer from input stream
    public long nextLong() throws java.io.IOException {

        if (readJunk(DASH-1) == EOF) throw new java.io.IOException();
        int sgn = 1;
        long res = 0L;
        c = buf[bufIndex];
        if (c == DASH) { sgn = -1; bufIndex++; }

        do {

            while(bufIndex < numBytesRead) {
                if (buf[bufIndex] > SP) {
                    res = (res<<3)+(res<<1);
                    res += ints[buf[bufIndex++]];
                } else {
                    bufIndex++;
                    return res*sgn;
                }
            }

            // Reload buffer
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF) return res*sgn;
            bufIndex = 0;

        } while(true);

    }

    // Double the size of the internal char buffer for strings
    private void doubleCharBufferSize() {
        char[] newBuffer = new char[charBuffer.length << 1];
        for(int i = 0; i < charBuffer.length; i++) newBuffer[i] = charBuffer[i];
        charBuffer = newBuffer;
    }

    // Reads a line from input stream.
    // Returns null if there are no more lines
    public String nextLine() throws java.io.IOException {

        try { c=read(); } catch (java.io.IOException e) { return null; }
        if (c == NL) return ""; // Empty line
        if (c == EOF) return null; // EOF

        int i = 0;
        charBuffer[i++] = (char)c;

        do {

            while(bufIndex < numBytesRead) {
                if (buf[bufIndex] != NL) {
                    if (i == charBuffer.length) doubleCharBufferSize();
                    charBuffer[i++] = (char) buf[bufIndex++];
                } else {
                    bufIndex++;
                    return new String(charBuffer, 0, i);
                }
            }

            // Reload buffer
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF)
                return new String(charBuffer, 0, i);
            bufIndex = 0;

        } while(true);

    }

    // Reads a string of characters from the input stream.
    // The delimiter separating a string of characters is set to be:
    // any ASCII value <= 32 meaning any spaces, new lines, EOF, tabs ...
    public String nextString() throws java.io.IOException {

        if (numBytesRead == EOF) return null;
        if (readJunk(SP) == EOF) return null;
        int i = 0;

        do {

            while(bufIndex < numBytesRead) {
                if (buf[bufIndex] > SP) {
                    if (i == charBuffer.length) doubleCharBufferSize();
                    charBuffer[i++] = (char) buf[bufIndex++];
                } else {
                    bufIndex++;
                    return new String(charBuffer, 0, i);
                }
            }

            // Reload buffer
            numBytesRead = stream.read(buf);
            if (numBytesRead == EOF) return new String(charBuffer, 0, i);
            bufIndex = 0;

        } while(true);

    }

    // Returns an exact value a double value from the input stream.
    public double nextDouble() throws java.io.IOException {
        String doubleVal = nextString();
        if (doubleVal == null) throw new java.io.IOException();
        return Double.valueOf(doubleVal);
    }

    // Very quickly reads a double value from the input stream (~3x faster than nextDouble()). However,
    // this method may provide a slightly less accurate reading than .nextDouble() if there are a lot
    // of digits (~16+). In particular, it will only read double values with at most 21 digits after
    // the decimal point and the reading my be as inaccurate as ~5*10^16 from the true value.
    public double nextDoubleFast() throws java.io.IOException {
        c = read(); int sgn = 1;
        while (c <= SP) c = read(); // while c is either: ' ', '\n', EOF
        if (c == DASH) { sgn = -1; c = read(); }
        double res = 0.0;
        // while c is not: ' ', '\n', '.' or -1
        while (c > DOT) {res *= 10.0; res += ints[c]; c = read(); }
        if (c == DOT) {
            int i = 0; c = read();
            // while c is digit and we are less than the maximum decimal precision
            while (c > SP && i < MAX_DECIMAL_PRECISION) {
                res += doubles[ints[c]][i++]; c = read();
            }
        }
        return res * sgn;
    }

    // Read an array of n byte values
    public byte[] nextByteArray(int n) throws java.io.IOException {
        byte[] ar = new byte[n];
        for (int i = 0; i < n; i++) ar[i] = nextByte();
        return ar;
    }

    // Read an array of n char values
    // Buggy method must patch
    // public char[] nextCharArray(int n) throws java.io.IOException {
    //   String str = nextString();
    //   if (str == null) return null;
    //   return str.toCharArray();
    // }

    // Read an integer array of size n
    public int[] nextIntArray(int n) throws java.io.IOException {
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) ar[i] = nextInt();
        return ar;
    }

    // Read a long array of size n
    public long[] nextLongArray(int n) throws java.io.IOException {
        long[] ar = new long[n];
        for (int i = 0; i < n; i++) ar[i] = nextLong();
        return ar;
    }

    // read an of doubles of size n
    public double[] nextDoubleArray(int n) throws java.io.IOException {
        double[] ar = new double[n];
        for (int i = 0; i < n; i++) ar[i] = nextDouble();
        return ar;
    }

    // Quickly read an array of doubles
    public double[] nextDoubleArrayFast(int n) throws java.io.IOException {
        double[] ar = new double[n];
        for (int i = 0; i < n; i++) ar[i] = nextDoubleFast();
        return ar;
    }

    // Read a string array of size n
    public String[] nextStringArray(int n) throws java.io.IOException {
        String[] ar = new String[n];
        for (int i = 0; i < n; i++) {
            String str = nextString();
            if (str == null) throw new java.io.IOException();
            ar[i] = str;
        }
        return ar;
    }

    // Read a 1-based byte array of size n+1
    public byte[] nextByteArray1(int n) throws java.io.IOException {
        byte[] ar = new byte[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextByte();
        return ar;
    }

    // Read a 1-based integer array of size n+1
    public int[] nextIntArray1(int n) throws java.io.IOException {
        int[] ar = new int[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextInt();
        return ar;
    }

    // Read a 1-based long array of size n+1
    public long[] nextLongArray1(int n) throws java.io.IOException {
        long[] ar = new long[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextLong();
        return ar;
    }

    // Read a 1-based double array of size n+1
    public double[] nextDoubleArray1(int n) throws java.io.IOException {
        double[] ar = new double[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextDouble();
        return ar;
    }

    // Quickly read a 1-based double array of size n+1
    public double[] nextDoubleArrayFast1(int n) throws java.io.IOException {
        double[] ar = new double[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextDoubleFast();
        return ar;
    }

    // Read a 1-based string array of size n+1
    public String[] nextStringArray1(int n) throws java.io.IOException {
        String[] ar = new String[n+1];
        for (int i = 1; i <= n; i++) ar[i] = nextString();
        return ar;
    }

    // Read a two dimensional matrix of bytes of size rows x cols
    public byte[][] nextByteMatrix(int rows, int cols) throws java.io.IOException {
        byte[][] matrix = new byte[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextByte();
        return matrix;
    }

    // Read a two dimensional matrix of ints of size rows x cols
    public int[][] nextIntMatrix(int rows, int cols) throws java.io.IOException {
        int[][] matrix = new int[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextInt();
        return matrix;
    }

    // Read a two dimensional matrix of longs of size rows x cols
    public long[][] nextLongMatrix(int rows, int cols) throws java.io.IOException {
        long[][] matrix = new long[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextLong();
        return matrix;
    }

    // Read a two dimensional matrix of doubles of size rows x cols
    public double[][] nextDoubleMatrix(int rows, int cols) throws java.io.IOException {
        double[][] matrix = new double[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextDouble();
        return matrix;
    }

    // Quickly read a two dimensional matrix of doubles of size rows x cols
    public double[][] nextDoubleMatrixFast(int rows, int cols) throws java.io.IOException {
        double[][] matrix = new double[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextDoubleFast();
        return matrix;
    }

    // Read a two dimensional matrix of Strings of size rows x cols
    public String[][] nextStringMatrix(int rows, int cols) throws java.io.IOException {
        String[][] matrix = new String[rows][cols];
        for(int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i][j] = nextString();
        return matrix;
    }

    // Read a 1-based two dimensional matrix of bytes of size rows x cols
    public byte[][] nextByteMatrix1(int rows, int cols) throws java.io.IOException {
        byte[][] matrix = new byte[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextByte();
        return matrix;
    }

    // Read a 1-based two dimensional matrix of ints of size rows x cols
    public int[][] nextIntMatrix1(int rows, int cols) throws java.io.IOException {
        int[][] matrix = new int[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextInt();
        return matrix;
    }

    // Read a 1-based two dimensional matrix of longs of size rows x cols
    public long[][] nextLongMatrix1(int rows, int cols) throws java.io.IOException {
        long[][] matrix = new long[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextLong();
        return matrix;
    }

    // Read a 1-based two dimensional matrix of doubles of size rows x cols
    public double[][] nextDoubleMatrix1(int rows, int cols) throws java.io.IOException {
        double[][] matrix = new double[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextDouble();
        return matrix;
    }

    // Quickly read a 1-based two dimensional matrix of doubles of size rows x cols
    public double[][] nextDoubleMatrixFast1(int rows, int cols) throws java.io.IOException {
        double[][] matrix = new double[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextDoubleFast();
        return matrix;
    }

    // Read a 1-based two dimensional matrix of Strings of size rows x cols
    public String[][] nextStringMatrix1(int rows, int cols) throws java.io.IOException {
        String[][] matrix = new String[rows+1][cols+1];
        for(int i = 1; i <= rows; i++)
            for (int j = 1; j <= cols; j++)
                matrix[i][j] = nextString();
        return matrix;
    }

    // Closes the input stream
    public void close() throws java.io.IOException {
        stream.close();
    }

}
