Annettuna on syklinen taulukko, jossa on n lukua. Syklisyys tarkoittaa, että kohdassa n olevan luvun jälkeen tulee taas kohdassa 1 oleva luku.

Tehtäväsi on jakaa taulukko yhtenäisiin väleihin niin, että jokaisen välin lukujen summa on enintään k. Mikä on pienin mahdollinen välien määrä?

Syöte

Syötteen ensimmäisellä rivillä on luvut n ja k.

Syötteen toinen rivi sisältää n lukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Mikään taulukon luku ei ole suurempi kuin k.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin välien määrä.

Rajat

• 1 \le n \le 10^5
• 1 \le x_i \le 10^9
• 1 \le k \le 10^{18}

Esimerkki

Syöte:

8 5
2 2 2 1 3 1 2 1

Tuloste:

3

Selitys: Jako on seuraava: "2 | 2 2 1 | 3 1 | 2 1". Huomaa, että yksi ryhmistä jatkuu taulukon lopusta alkuun.