1 \(s / 64\) \(MB / 120\) points

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 {1}{ } is of good quality.
Such expression is of the following form:
(x)
●
For example, if Z {1}{ } = 5, then (4) is a quality expression.
●
If A {1}{ }, A {2}{ }, ..., 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 {1}{ }+A {2}{ }+...+A {k}{ })
(A {1}{ }A {2}{ }...*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 \le K \le 50\)).
The second line of input contains integers Z {1}{ }, ..., Z {K,}{ }, separated by space (\(1 \le Z\) {1}{ }, ..., 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}\).

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 3