Delnice

Vaš prijatelj se hvali, da je nedavno z nakupom in kasnejšo prodajo ene same delnice nekega podjetja zaslužil $Z$ evrov. Ker dvomite v njegove trgovalne sposobnosti (v njegovo sposobnost samohvale pa ne), ste se odločili stvar raziskati. Zato ste pridobili dnevne spremembe $d_i$ v ceni omenjene delnice za zadnjih $N$ dni. To pomeni, da če ste kupili delnico $i$-ti dan zjutraj, ste jo lahko ob koncu istega dne prodali za $d_i$ evrov višjo ceno. Predpostavimo, da čez noč ne prihaja do sprememb v ceni. Kako zelo se lahko približate zaslužku $Z$ z enim nakupom in prodajo delnice (isti ali kakšen kasnejši dan)?

Omejitve podatkov:

• $1 \leq N \leq 10^6$
• $|x_i| \leq 10^9$
• $|Z| \leq 10^{18}$

Vhodni in izhodni podatki:

V prvi vrstici sta podani število dni $N$ in ciljni zaslužek $Z$ (ki je lahko tudi negativen). V drugi vrstici je $N$ s presledkom ločenih celih števil $d_i$, ki predstavljajo spremembo v ceni delnice tisti dan.

Izpišite, za koliko enot se lahko najbolj približate ciljnemu zaslužku z nakupom in prodajo delnice v enem strnjenem časovnem obdobju. Zanima nas absolutna razlika, zato mora biti izpisana vrednost večja ali enaka 0.

Primer vhoda:

20 74
-18 -100 -91 -99 80 79 71 -60 34 0 -71 -41 11 -2 -51 65 -23 36 -6 94

Pravilen izhod:

2

Če kupimo delnico na začetku 16. dneva in jo prodamo na koncu 19. dneva, bomo zaslužili 65 + (-23) + 36 + (-6) = 72, kar se od ciljne vrednosti 74 razlikuje za 2 enoti.