配点 : $100$ 点

問題文

無限個の項からなる数列 $a_1,$ $a_2,$ $\cdots$ を考えます。はじめ、すべての項の値は $0$ であり、この状態から $Q$ 回の操作を続けて行います。$i$ 回目の操作 $(1 \leq i \leq Q)$ は次の通りです。

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$Q$

$m_1$ $x_1$

$:$

$m_Q$ $x_Q$

出力

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

3
2 10
3 -20
6 15

10

数列の各項 $a_1,$ $a_2,$ $\cdots$ の値は以下のように変化します。

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

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

3
10 -3
50 4
100 -5

1

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

438699