maxs

A group of $n$ bunnies found a garden with $n$ carrots, arranged in a row. Both the bunnies and the carrots are numbered with integers from $1$ to $n$. The bunnies have made preliminary evaluation for the sweetness of the carrots, which are expressed with the integers $a_1, ..., a_n$ (some carrots may be spoiled and can have negative number for sweetness). The soil under only one carrot $p$ is fertilized and this changes the sweetness of this carrot by an integer $s$. More precisely, the real sweetness of carrot $p$ is $a_p + s$.

Unfortunately, $p$ and $s$ are unknown to rabbits. However, they have $m$ assumptions about the pair of values $(p, s)$.

Bunny number $k$ makes jumps of length $k$, i.e. collects the carrots in positions that are multiples of $k$.

For each assumption $j$, they look for the maximum amount $t_j$ of the total real sweetness of the carrots that can be collected by a bunny. Help them by writing program that finds the sum of the values of $t_j$ for all assumptions.

Input

From the first line of the standard input, your program reads an integer $n$ - the number of carrots (and bunnies). From the next line read $n$ integers $a_1, ..., a_n$ - the preliminary evaluation of the sweetness of the carrots. From the next line read an integer $m$ - the number of assumptions. From each of the next $m$ lines, read two integers $p$ and $s$ - carrot's index and its' sweetness change for the corresponding assumption.

Output

On one line of the standard output, print a number equal to $t_1 + ... + t_m$, where $t_j$ is the maximum sum of carrots' sweetness under the $j$-th assumption.

Constraints

• $1 ≤ n ≤ 5 \cdot 10^4$
• $1 ≤ m ≤ 5 \cdot 10^5$
• $−10^8 ≤ a_i ≤ 10^8$
• $1 ≤ p ≤ n$ for each carrot's index $p$
• $−10^{13} ≤ s ≤ 10^{13}$ for any change in sweetness $s$

Subtask 1 (0 points)

• Sample test

Subtask 2 (13 points)

• $n \leq 5 \cdot 10^3$
• $m \leq 5 \cdot 10^3$

Subtask 3 (21 points)

• $n \leq 1.5 \cdot 10^4$
• $m \leq 3.5 \cdot 10^3$

Subtask 4 (25 points)

• $m \leq 2 \cdot 10^5$
• Only non-negative changes in any sweetness $s$.

Subtask 5 (30 points)

• $m \leq 2 \cdot 10^5$

Subtask 6 (11 points)

• No additional constraints

Example

stdin

6
2 -5 3 2 -1 4
2
3 -4
2 3

stdout

12

Explanation

According to the first assumption, carrots have sweetness 2, -5, -1, 2, -1, 4.
Bunny 1 collects total sweetness 2 + (-5) + (-1) + 2 + (-1) + 4 = 1.
Bunny 2 collects total sweetness (-5) + 2 + 4 = 1.
Bunny 3 collects total sweetness (-1) + 4 = 3.
Bunny 4 collects total sweetness 2.
Bunny 5 collects total sweetness of -1.
Bunny 6 collects total sweetness 4.
Therefore t1 = 4.
According to the second assumption, carrots have sweetness 2, -2, 3, 2, -1, 4.
Bunnies collect sweetness 8, 4, 7, 2, -1, 4, respectively.
Therefore t2 = 8.
The final answer is 4 + 8 = 12.