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\le 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\le n\le {10}^5$, $1\le d\le {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\le a_i\le {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