← 返回题目列表

AtCoder · relay2_h

H. 阿卡西记录

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

考虑一个无限序列 a_1, a_2, … 最初,所有项的值为 0,从这个状态我们将依次执行 Q 操作。的 i第次操作 (1 ≤ i ≤ Q) 如下:

  • 对于每个正整数 j,添加 x_i 的值 a_{j × m_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-st 操作: 0, 10, 0, 10, 0, 10, …
  • 之后 2-nd操作: 0, 10, -20, 10, 0, -10, …
  • 之后 3-rd操作: 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