Hide

Problem E
Maximum Expression

/problems/maxexpression/file/statement/en/img-0001.jpg
Image by eminens

There is an expression with $n$ question marks, and $n-1$ operators between them. The operators only include addition, subtraction, and multiplication. Here is an example:

?+?-?*?+?*?*?

You are going to replace every question mark with a digit from $\{ 0, 1, 2\} $. After the replacement, there should be exactly $n_0$, $n_1$, and $n_2$ occurrences of $0$, $1$, and $2$ respectively. Can you maximize the value of the expression by finding the best arrangement of the digits?

Input

The first line has a single integer $n$ ($2 \leq n \leq 5\, 000$). The second line gives the expression, with no white spaces between characters. The third line has three non-negative integers $n_0$, $n_1$, and $n_2$ ($n_0 + n_1 + n_2 = n$).

It is guaranteed that the expression does not have more than $50$ consecutive question marks with only multiplication operators between them.

Output

Output the maximum value of the expression.

Sample Input 1 Sample Output 1
7
?+?-?*?+?*?*?
1 2 4
11

Please log in to submit a solution to this problem

Log in