分数: 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