20873번 - Företagsrykte 다국어

Du har just startat ett företag. Du vet att det företaget sysslar med inte är jättepopulärt -- varje dag $i$ under de kommande $n$ dagarna räknar du med att ditt rykte kommer försämras med något givet värde $r_i$. Du kommer därefter även förlora lika mycket pengar som ditt rykte är dåligt. Under natten har du möjlighet att nollställa ditt rykte, genom att byta namn på företaget. Detta går att göra hur många gånger som helst, men kostar en fix summa $k$.

Vilken är den minsta förlust du kan uppnå?

Den första raden innehåller två heltal $n$, och $k$ ($2 \leq n \leq 4 \cdot 10^5$, $0 \leq k \leq 2 \cdot 10^9$). Den andra raden innehåller $n$ tal $r_i$ ($1 \le r_i \le 10^6$) -- hur mycket ditt rykte ditt rykte kommer försämras under dag $i$.

Ett tal, den minsta förlusten du kan uppnå.