시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 8 4 4 50.000%

문제

A quality arithmetic expression consists of brackets, number 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 Z1 is of good quality.
    Such expression is of the following form:
    (x)
    For example, if Z1 = 5, then (4) is a quality expression.
  • If A1 , A2 , …, Ak are quality expressions such that 2 k K and ≤ ≤ the sum​ of these expressions is at most Zk , then the following expressions are of good quality:
    (A1+A2+...+Ak )
    (A1 *A2 *...*Ak )

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. 

입력

The first line of input contains integer K (2 ≤ K ≤ 50).

The second line of input contains integers Z1 , …, ZK, separated by space (1 ≤ Z1 , …, ZK ≤ 50).

The third line of input contains one quality arithmetic expression in the described format. Arithmetic expression consists of: ‘?’, ‘*’, ‘+’, ‘(‘, ‘)’, and its length is 1 000 000 characters, at most. 

출력

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 10-3

예제 입력

2
10 6
((?)+(?))

예제 출력

6.00000

예제 입력 2

3
2 5 3
(((?)+(?))*(?))

예제 출력 2

6.00000

예제 입력 3

3
2 10 6
((?)*(?)*(?))

예제 출력 3

8.000000000

힌트

The expression ((3)+(3)) satisfies the conditions, so it is a quality expression, and it is easy to check that 6 is the maximal value.