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?

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 the maximum value of the expression.

Sample Input 1 | Sample Output 1 |
---|---|

7 ?+?-?*?+?*?*? 1 2 4 |
11 |