Bank Statement Correction

Byteasar has an account at The Byteotian Bit Bank (BBB). Initially, his account holds \(p\) bythalers. After a sequence of transactions – each of which is either a deposit or a withdrawal of one bythaler – the account balance becomes \(q\) bythalers. The bank teller has printed a bank statement recorded as a sequence of pluses and minuses (+ denotes a deposit and - denotes a withdrawal). Unfortunately, some transactions may have been recorded incorrectly.

The teller can perform two types of correction operations:

• In \(x\) seconds, flip an arbitrarily chosen transaction (i.e. change a + to a - or vice versa).
• In \(y\) seconds, remove the last transaction and insert it at the beginning of the statement (a cyclic rotation by one).

The corrected statement must satisfy both of the following conditions:

1. The final balance, computed from the initial balance \(p\) and the corrected sequence of transactions, equals \(q\):
   \(p + \sum_{i=1}^{n} a_i = q\), where \(a_i = 1\) for a deposit and \(a_i = -1\) for a withdrawal.
2. The account's balance never becomes negative when the transactions are applied sequentially (i.e. for all prefixes \(j\),
   \(p + \sum_{i=1}^{j} a_i \ge 0\)).

Your task is to compute the minimum number of seconds required to perform corrections on the printed statement so that it meets the above conditions. Note that the corrected statement does not need to reflect the original sequence of transactions accurately; it only needs to satisfy the consistency requirements.

Input constraints and Operations:

• You are given a string consisting solely of '+' and '-' characters representing the transactions.
• You are given four integers \(p, q, x, y\), where \(x\) is the cost in seconds to flip a transaction and \(y\) is the cost to rotate the last transaction to the front.

Note: If the printed statement is of length \(n\), then performing \(r\) rotations results in a cyclic shift of the string (each rotation moves the last character to the beginning, at cost \(y\) per rotation). The corrections (flips) are applied on the rotated sequence. Each flip on a '+' changes it to '-' (affecting the balance by \(-2\)) and each flip on a '-' changes it to '+' (affecting the balance by \(+2\)).

Formally, if the original transaction value is represented as \(v_i\) (with \(v_i = 1\) for '+' and \(v_i = -1\) for '-'), upon flipping the transaction becomes \(-v_i\). Hence, if a transaction is flipped, the change in balance is \( -2v_i \); if it is left unchanged, the change is \( v_i \). The overall effect must satisfy:

[ p + \sum_{i=1}^{n} (1 - 2\cdot F_i),v_i = q, ]

where \(F_i\) is 1 if the \(i^\text{th}\) transaction is flipped and 0 otherwise, and the balance must remain nonnegative after each transaction.

Your programme should compute the minimum total cost (in seconds) consisting of the cost for flips and rotations required to correct the statement.

inputFormat

The input is read from standard input. It contains two lines:

• The first line contains a non-empty string consisting only of the characters '+' and '-'. This is the bank statement.
• The second line contains four space‐separated integers \(p\), \(q\), \(x\), and \(y\), where \(p\) is the initial balance, \(q\) is the desired final balance, \(x\) is the cost to flip a transaction, and \(y\) is the cost to perform one rotation.

outputFormat

Output a single integer representing the minimum number of seconds required to correct the bank statement so that the account's final balance is \(q\) and the balance never becomes negative during the sequence of transactions.

sample

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

0