Contest Duration: ~ (local time)
H - Akashic Records

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

• すべての正の整数 j に対し、a_{j × m_i} の値に x_i を加える。

これらの Q 回の操作後の最も大きい項の値を求めてください。

### 制約

• 1 ≤ Q ≤ 299
• 2 ≤ m_i ≤ 300
• -10^6 ≤ x_i ≤ 10^6
• m_i はすべて異なる。
• 入力値はすべて整数である。

### 入力

Q
m_1 x_1
:
m_Q x_Q


### 出力

Q 回の操作後の最も大きい項の値を出力せよ。

### 入力例 1

3
2 10
3 -20
6 15


### 出力例 1

10


• 操作前: 0, 0, 0, 0, 0, 0,
• 1 回目の操作後: 0, 10, 0, 10, 0, 10,
• 2 回目の操作後: 0, 10, -20, 10, 0, -10,
• 3 回目の操作後: 0, 10, -20, 10, 0, 5,

すべての操作後の最も大きい項の値は 10 です。

### 入力例 2

3
10 -3
50 4
100 -5


### 出力例 2

1


### 入力例 3

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


### 出力例 3

438699


Score : 100 points

### Problem Statement

Consider an infinite sequence a_1, a_2, Initially, the values of all the terms are 0, and from this state we will sequentially perform Q operations. The i-th operation (1 ≤ i ≤ Q) is as follows:

• For every positive integer j, add x_i to the value of a_{j × m_i}.

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

### Constraints

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

### Input

Input is given from Standard Input in the following format:

Q
m_1 x_1
:
m_Q x_Q


### Output

Print the value of the largest term after the Q operations.

### Sample Input 1

3
2 10
3 -20
6 15


### Sample Output 1

10


The values of each terms in the sequence a_1, a_2, change as follows:

• Before the operations: 0, 0, 0, 0, 0, 0,
• After the 1-st operation: 0, 10, 0, 10, 0, 10,
• After the 2-nd operation: 0, 10, -20, 10, 0, -10,
• After the 3-rd operation: 0, 10, -20, 10, 0, 5,

The value of the largest term after all the operations is 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