Băieţii de la 808 vor să organizeze o întrecere cu ripstick-urile. Ei au stabilit N trasee, fiecare dintre acestea având un anumit grad de solicitare, S[i] (1<=i<=N), reprezentat printr-un număr întreg. Băieţii s-au hotărât să împartă concursul în mai multe runde, între care să existe o pauză de odihnă. O rundă poate să fie formată dintr-un număr oarecare de trasee consecutive. Gradul de solicitare al rundei este egal cu suma gradelor de solicitare ale fiecărui traseu din runda respectivă. Se ştie că pauza dintre două runde poate să micşoreze gradul de solicitare al rundei anterioare, acesta luând valoarea A, doar dacă gradul iniţial se află în intervalul [A, B].
Cerinţă
Băieţii de la camera 808 vă roagă să-i ajutaţi să calculeze suma minimă a gradelor de dificultate ale tuturor rundelor.
Date de intrare
Fişierul de intrare ripstick.in
conţine pe prima linie 3 numere naturale NAB cu semnificaţiile din enunţ. Pe cea de a doua linie se află N numere întregi. Al i-lea număr reprezintă gradul de solicitare S[i] al celui de al i-lea traseu.
Date de ieşire
Fişierul de ieşire ripstick.out
va conţine o singură linie pe care va fi scris un număr întreg, reprezentând suma minimă obţinută.
Restricţii
1 <= N <= 100 000
1 < A, B <= 1 000 000 000
-10 000 <= S[i] <= 10 000
Pentru 20% din teste 1 <= N <= 1 000
Pentru alte 20% din teste 0 <= S[i]
Un traseu poate să fie mai mult relaxant decât solicitant, deci gradul de solicitare poate fi negativ.
Fiecare traseu trebuie să aparţină exact unei runde.
Exemplu
ripstick.in
ripstick.out
4 17 27
3 12 10 9
26
Alexandru Cazacu
Facultatea de Matematică şi Informatică - Universitatea Bucureşti