Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 64M

Problem type

Pera ima N gajbica poređanih u nizu, u kojima se nalaze jabuke. U i-toj gajbici se nalazi A_i jabuka. Pera ne voli kada mu se u neke dve uzastopne gajbice nalazi u zbiru više od K jabuka, i zbog toga će on baciti neke jabuke iz nekih gajbica.

Koliko najmanje jabuka Pera može da baci, tako da se u svake dve uzastopne gajbice nalazi najviše K jabuka?

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se dva broja odvojena razmakom N i K. U drugoj liniji standardnog ulaza nalazi se N brojeva odvojenih razmakom, koje predstavljaju niz A, odnosno broj jabuka redom u gajbicama.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati minimalni broj jabuka koje Pera može da baci da bi ispunio uslov iz zadatka.

Primer
Standardni ulaz          Standardni izlaz
3 4
3 3 2
2
5 10
6 7 8 9 5
10
Objašnjenje test primera

U prvom test primeru prva i druga gajbica imaju u zbiru 6 jabuka, dok druga i treća imaju u zbiru 5 jabuka, što je veće od 4 koliko je dozvoljeno. Ukoliko iz druge gajbice izvadimo 2 jabuke ostaće nam {3, 1, 2}, pa će u prve dve uzastopne zbir biti 4, a u druge dve 3, što nije veće od 4.

U drugom test primeru možemo u svakoj gajbici ostaviti po tačno 5 jabuka, iz prve ćemo izbaciti 1, iz druge 2, iz treće 3 i iz četvrte 4 jabuke, što je u zbiru 10 jabuka. Ne može se postići željeni uslov izbacivanjem manje od 10 jabuka.

Ograničenja i podzadaci

(1 \le N \le 10^5)
(0 \le K, A_i \le 10^9)


Comments

There are no comments at the moment.