Maximal sum

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, \dots, 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 the bunnies. However, they have 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 maxs that finds the sum of the values of $t_j$ for all assumptions.

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, \dots, 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.

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

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

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 $t_1 = 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 $t_2 = 8$.

The final answer is $4 + 8 = 12$.