Problem : 29 - BBB

Problem Statistics

Solved Member: 16　　Submission: 98　　User Tried: 18

Statement:

你正在拜特蘭位元銀行(Byteotian Bit Bank , 簡稱BBB)當經理。今天你正在檢查你的職員們所記錄的帳戶報表，發現另你抓狂的事情－－他們做記錄的報表是錯的！！這個帳戶一開始有p拜特幣，最終有q拜特幣。每次提款或存款只有2種可能，存入1拜特幣或者領出1拜特幣。在報表當中，以正號(+)來表示存入1拜特幣，以負號(-)來表示提出1拜特幣。你必須把這個報表改成合理的，所謂合理的報表必須要滿足以下2個條件：

1.最後的結餘必須和報表是相符合的。
2.帳戶的餘額只會大於或等於0，也就是說餘額不會出現負的。

你想要知道你更正這個報表最少需要的時間，你可以：

1.花x秒把一個正號改成負號，或者把負號改成正號。
2.花y秒把最後一次交易記錄移到最前面。

例如，p=2 , q=3時，--++-+-++-+-+是一個正確的報表。相反地---++++++是錯誤的。第一，它在某個時間的帳戶餘額是負的，第二，它的結餘5，並不是3。你可以把倒數第2筆交易的正號改成負號，並且把最後一次交易移到第1筆，只需要花3的時間即可修正報表。

Task:

請你寫一個程式來達成下面任務：
1.讀入p,q,x,y和報表的序列。
2.輸出更正報表所需要的最少時間。

Input:Output:

第1行有5個整數。n,p,q,x,y，以空格分開，並且滿足1 <= n <= 1000000，0 <= p,q <= 1000000，1 <= x,y <= 1000。
這5個整數分別代表報表的交易數量，銀行最初的存款，最後的結餘，以及兩項操作所需要的時間。

第2行有一個長度為n的序列，由加號和減號組成，代表報表的紀錄。

輸出一個整數，為更正報表最少所需要的時間。

Sample Input:Sample Output:

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

Source:

POI 15 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1-1	1000ms	32768kb	7
1-2	1000ms	32768kb
2-ocen	1000ms	32768kb
2-1	1000ms	32768kb	7
2-2	1000ms	32768kb
3-ocen	1000ms	32768kb
3-1	1000ms	32768kb	7
3-2	1000ms	32768kb
4-ocen	1000ms	32768kb
4-1	1000ms	32768kb	7
4-2	1000ms	32768kb
5-ocen	5000ms	32768kb
5-1	1000ms	32768kb	8
5-2	1000ms	32768kb
6	1000ms	32768kb	8
7	1000ms	32768kb	8
8	1000ms	32768kb	8
9-1	1000ms	32768kb	8
9-2	1000ms	32768kb
10	1000ms	32768kb	8
11	1000ms	32768kb	8
12	1000ms	32768kb	8
13-1	1000ms	32768kb	8
13-2	1000ms	32768kb