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 N A B 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

alexandru.cazacu92@gmail.com