A quality arithmetic expression consists of brackets, numbers and operations of multiplication and addition.
A quality arithmetic expression is defined recursively in the following way:
- An expression consisting of only one positive real number smaller than or equal to is of good quality. For example, if , then is a quality expression.
- If are quality expressions such that and the sum of these expressions is at most , then the following expressions are of good quality:
You are given a quality expression where the numbers are replaced by question marks. Determine the maximal possible value that the expression could have had.
Input Specification
The first line of input contains integer .
The second line of input contains integers , separated by spaces .
The third line of input contains one quality arithmetic expression in the described format.
An arithmetic expression consists of: ?
, *
, +
, (
, )
, and its length is at most characters.
Output Specification
You must output the maximal possible value of the expression.
A solution is considered correct if the absolute or relative deviation from the official solution is less than .
Sample Input 1
2
10 6
((?)+(?))
Sample Output 1
6.00000
Explanation for Sample Output 1
The expression ((3)+(3))
satisfies the conditions, so it is a quality expression, and it is easy to check that is the maximal value.
Sample Input 2
3
2 5 3
(((?)+(?))*(?))
Sample Output 2
6.00000
Explanation for Sample Output 2
The maximum is achieved for, for instance, the expression (((1)+(2))*(2))
.
Sample Input 3
3
2 10 6
((?)*(?)*(?))
Sample Output 3
8.000000000
Explanation for Sample Output 3
The maximum is achieved for, for instance, the expression ((2)*(2)*(2))
.
Comments