BBB

Limit pamięci: 32 MB

Bajtazar ma konto w Bajtockim Banku Bitowym (w skrócie BBB). Na początku na koncie było a na końcu bajtalarów. Wszystkie transakcje polegały na wpłacie bądź wypłacie jednego bajtalara. Bilans konta nigdy nie zszedł poniżej zera. Kasjer przygotował wyciąg z konta: pasek papieru z ciągiem plusów i minusów (plus oznacza wpłatę a minus wypłatę jednego bajtalara). Okazało się, że operacje wykonywane na koncie nie zawsze były poprawnie księgowane. Kasjer nie może wydrukować nowego wyciągu, lecz musi poprawić ten już wydrukowany. Wyciąg nie musi być zgodny z rzeczywistością, wystarczy, że ciąg operacji na wyciągu będzie spełniał następujące dwa warunki:

• saldo końcowe będzie się zgadzać z saldem początkowym i ciągiem operacji na wyciągu,
• zgodnie z ciągiem operacji na wyciągu, saldo konta nigdy nie spadło poniżej zera.

Kasjer może:

• w ciągu sekund zmienić wybraną operację na wyciągu na przeciwną, lub
• w ciągu sekund przenieść ostatnią operację na początek wyciągu.

Jeśli to na przykład --++-+-++-+-+ jest poprawnym wyciągiem. Natomiast wyciąg ---++++++ nie jest poprawny, gdyż po trzeciej operacji saldo konta spadłoby poniżej zera, a ponadto saldo końcowe powinno wynosić 3, a nie 5. Możemy go jednak poprawić, zmieniając przedostatni symbol na przeciwny i następnie przenosząc ostatnią operację na początek wyciągu.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia aktualny wygląd wyciągu z konta Bajtazara (ciąg plusów i minusów) oraz liczby , , i ,
• wypisze na standardowe wyjście minimalną ilość czasu, potrzebną na taką korektę wyciągu, żeby początkowy i końcowy bilans się zgadzały oraz żeby saldo konta w żadnym momencie nie spadło poniżej zera.

Wejście

Pierwszy wiersz zawiera 5 liczb całkowitych , , , oraz (, , ), pooddzielanych pojedynczymi odstępami i oznaczających odpowiednio: liczbę transakcji wykonanych przez Bajtazara, początkowe i końcowe saldo konta oraz liczby sekund potrzebne na wykonanie pojedynczej zamiany i przesunięcia operacji na wyciągu. Drugi wiersz zawiera ciąg plusów i/lub minusów, niezawierający odstępów.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnemu czasowi potrzebnemu do poprawienia wyciągu. Jeśli wyciąg nie wymaga poprawek, tą liczbą powinno być zero. Możesz założyć, że odpowiedni ciąg modyfikacji wyciągu będzie istniał dla każdych danych testowych.

Przykład

Dla danych wejściowych:

9 2 3 2 1
---++++++

poprawną odpowiedzią jest:

3

Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.