돈

이미지 출처: 플리커닷컴

Tómas는 이상한 세계에 있다. 이 세계는 원형으로 배치된 $n$개의 칸으로 이루어져 있다. 따라서 $1 \leq i < n$에 대해 $i$번 칸과 $i+1$번 칸은 서로 이웃하며, 또한 $1$번 칸과 $n$번 칸도 서로 이웃한다. 각 칸에는 $a_i$만큼의 돈이 있다. Tómas는 처음에 $1$번 칸에서 시작한다. 각 단계에서 그는 앞으로 $d$칸 이동한다. Tómas는 각 칸에 있는 돈을 모두 가져간다. 더 이상 돈을 얻을 수 없을 때까지 이 과정을 계속한다면 Tómas가 얼마의 돈을 가지게 되는지 구하여라.

채점

그룹 | 점수 | 제한

1 | 25 | $1 \leq n, a_i \leq 100$, $d = 1$

2 | 25 | $1 \leq n, d, a_i \leq 100$

3 | 50 | 추가 제한 없음

입력의 첫째 줄에는 두 정수 $n,d$ ($1 \leq n \leq 10^5$, $1 \leq d \leq 10^{14}$)가 주어진다. 여기서 $n$는 칸의 수이고, $d$는 Tómas가 각 단계에서 앞으로 이동하는 칸의 수이다.

다음 줄에는 $n$개의 정수 $a_i$ ($1 \leq a_i \leq 10^9$)가 주어지며, 이는 $i$번 칸에 있는 돈의 양을 나타낸다.

Tómas가 최종적으로 가지게 되는 돈의 양을 나타내는 정수 하나를 출력한다.