実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 100 点
問題文
無限個の項からなる数列 a_1, a_2, … を考えます。はじめ、すべての項の値は 0 であり、この状態から Q 回の操作を続けて行います。i 回目の操作 (1 ≤ i ≤ Q) は次の通りです。
- すべての正の整数 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
数列の各項 a_1, a_2, … の値は以下のように変化します。
- 操作前: 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