최대 합

토끼 n마리가 당근 n개가 일렬로 심어진 밭을 발견했다. 토끼와 당근에는 각각 1부터 n까지의 정수가 붙어 있다. 토끼들은 당근의 단맛을 미리 평가했고, 그 값은 정수 $a_1, \dots, a_n$으로 주어진다. 상한 당근도 있을 수 있으므로 단맛이 음수일 수 있다. 당근 p 하나의 아래에 있는 흙에만 비료가 뿌려져 있고, 이 때문에 그 당근의 단맛이 정수 s만큼 변한다. 정확히는 당근 p의 실제 단맛은 $a_p + s$이다.

아쉽게도 토끼들은 p와 s를 모른다. 대신 값 쌍 (p, s)에 대한 가정을 여러 개 세워 두었다.

토끼 k는 길이 k만큼 점프한다. 즉, 번호가 k의 배수인 위치의 당근을 모은다.

각 가정 j마다 토끼가 모을 수 있는 당근의 실제 단맛 합의 최댓값 $t_j$를 구한다. 모든 가정에 대한 $t_j$의 합을 구하는 프로그램 maxs를 작성하라.

첫째 줄에서 정수 n이 주어진다. n은 당근의 개수이자 토끼의 수이다. 둘째 줄에서 정수 $a_1, \dots, a_n$이 주어진다. 이는 당근의 단맛을 미리 평가한 값이다. 셋째 줄에서 정수 m이 주어진다. m은 가정의 개수이다. 다음 m개 줄에서 각각 정수 p와 s가 주어진다. p는 당근의 번호이고, s는 해당 가정에서 그 당근의 단맛이 변하는 값이다.

표준 출력의 한 줄에 $t_1 + \dots + t_m$을 출력한다. 여기서 $t_j$는 j번째 가정에서 당근 단맛 합의 최댓값이다.

• $1 \le n \le 5 \times 10^4$
• $1 \le m \le 5 \times 10^5$
• $-10^8 \le a_i \le 10^8$
• 각 당근의 번호 p에 대해 $1 \le p \le n$
• 단맛의 변화 s에 대해 $-10^{13} \le s \le 10^{13}$

첫 번째 가정에서 당근의 단맛은 2, -5, -1, 2, -1, 4이다.

토끼 1은 단맛의 합 $2 + (-5) + (-1) + 2 + (-1) + 4 = 1$을 모은다.

토끼 2는 단맛의 합 $(-5) + 2 + 4 = 1$을 모은다.

토끼 3은 단맛의 합 $(-1) + 4 = 3$을 모은다.

토끼 4는 단맛 2를 모은다.

토끼 5는 단맛 -1을 모은다.

토끼 6은 단맛 4를 모은다.

따라서 $t_1 = 4$이다.

두 번째 가정에서 당근의 단맛은 2, -2, 3, 2, -1, 4이다. 토끼들은 각각 단맛 8, 4, 7, 2, -1, 4를 모은다.

따라서 $t_2 = 8$이다.

최종 답은 $4 + 8 = 12$이다.