Problem Description

Consider an infinite sequence $ a_1, $ $ a_2, $ $ … $. Initially, all terms are $ 0 $, and from this state, we will perform $ Q $ operations. The $ i $ -th operation $(1\ \leq\ i\ \leq\ Q)$ is as follows:

• For all positive integers $ j $, add $ x_i $ to the value of $a_{j\ \times\ m_i}$.

Find the value of the largest term after these $ Q $ operations.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ m_1 $ $ x_1 $ $ : $ $ m_Q $ $ x_Q $

Output Format

Output the value of the largest term after $ Q $ operations.

Sample Input and Output

Sample Input #1

3
2 10
3 -20
6 15

Sample Output #1

10

Sample Input #2

3
10 -3
50 4
100 -5

Sample Output #2

1

Sample Input #3

5
56 114834
72 -149861
100 190757
192 -132693
240 133108

Sample Output #3

438699

Notes/Hints

Constraints

• $1\ \leq\ Q\ \leq\ 299$
• $2\ \leq\ m_i\ \leq\ 300$
• $-10^6\ \leq\ x_i\ \leq\ 10^6$
• All $ m_i $ are distinct.
• All input values are integers.

Sample Explanation 1

The values of each term $ a_1, $ $ a_2, $ $ … $ of the sequence change as follows:
- Before operations: $ 0, $ $ 0, $ $ 0, $ $ 0, $ $ 0, $ $ 0, $ $ … $
- After the 1st operation: $ 0, $ $ 10, $ $ 0, $ $ 10, $ $ 0, $ $ 10, $ $ … $
- After the 2nd operation: $ 0, $ $ 10, $ $ -20, $ $ 10, $ $ 0, $ $ -10, $ $ … $
- After the 3rd operation: $ 0, $ $ 10, $ $ -20, $ $ 10, $ $ 0, $ $ 5, $ $ … $
The value of the largest term after all operations is $ 10 $.

见题面 Input 部分

见题面 Output 部分