13942번 - Kvalitetni 스페셜 저지다국어

문제

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 Z₁ is of good quality.
  Such expression is of the following form:
  (x)
  For example, if Z₁ = 5, then (4) is a quality expression.
• If A₁ , A₂ , …, A_k are quality expressions such that 2 k K and ≤ ≤ the sum​ of these expressions is at most Z_k , then the following expressions are of good quality:
  (A₁+A₂+...+A_k )
  (A₁ *A₂ *...*A_k )

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 Z₁ , …, Z_K, separated by space (1 ≤ Z₁ , …, Z_K ≤ 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 .

제한

힌트

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.