Start

2020-03-21 03:00 AKDT

Beta 2020

End

2020-03-21 08:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -114 days 0:07:18

Time elapsed

5:00:00

Time remaining

0:00:00

Problem P
Peningar

/problems/iceland.peningar/file/statement/is/img-0001.jpg
Mynd fengin af flickr.com

Tómas er staðsettur í skrítnum heimi. Heimurinn samanstendur af $n$ reitum í hring. Þannig eru reitir $i$ og $i+1$ hlið við hlið fyrir $1 \leq i < n$, og einnig eru reitir $1$ og $n$ hlið við hlið. Í hverjum reit er $a_ i$ mikið af peningum. Tómas byrjar upprunulega í reit $1$. Í hverju skrefi labbar hann um $d$ reiti áfram. Í hverjum reit tekur Tómas alla peningana sem eru í þeim reit. Getur þú sagt okkur hversu mikið af peningum Tómas mun hafa, ef hann heldur þessu áfram þangað til hann getur ekki fengið meiri pening?

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n,d$ ($1 \leq n \leq 10^5$, $1 \leq d \leq 10^{14}$), þar sem $n$ er fjöldi reita og $d$ er hversu mikið Tómas hoppar áfram í hverju skrefi.

Næsta lína inniheldur $n$ heiltölur, $a_ i$ ($1 \leq a_ i \leq 10^9$), sem táknar hversu mikið af peningum eru í reit $i$.

Úttak

Skrifa á út eina heiltölu, hversu mikið af peningum Tómas mun enda með.

Stigagjöf

Hópur

Stig

Takmarkanir

1

25

$1 \leq n, a_ i \leq 100$, $d = 1$

2

25

$1 \leq n, d, a_ i \leq 100$

3

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
4 1
1 1 1 1
4
Sample Input 2 Sample Output 2
4 2
1 5 3 5
4
Sample Input 3 Sample Output 3
5 3
1 2 3 4 5
15