Problem D
Peningar

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

4 1
1 1 1 1

4

4 2
1 5 3 5

4

5 3
1 2 3 4 5

15