Một biểu thức số học hoàn mỹ bao gồm các dấu ngoặc đơn, các số, với các phép toán nhân và cộng.

Một biểu thức số học hoàn mỹ được định nghĩa một cách đệ quy như sau:

• Một biểu thức chứa một số thực dương duy nhất nhỏ hơn hoặc bằng ~Z_1~ được coi là hoàn mỹ. Nó có dạng như sau: (x). Ví dụ như nếu ~Z_1=5~ thì (4) là một biểu thức số học hoàn mỹ.
• Nếu ~A_1,...,A_k~ ~(2 \leq k \leq K)~ là các biểu thức số học hoàn mỹ và tổng giá trị của các biểu thức không vượt quá ~Z_k~, thì những biểu thức sau được coi là hoàn mỹ: (A1+A2+...+Ak) và (A1*A2*...*Ak).

Bạn được cho một biểu thức số học hoàn mỹ với các số được thay thế bằng các dấu chấm hỏi. Hãy tìm giá trị lớn nhất có thể đạt được của biểu thức.

Input

Dòng đầu tiên chứa số nguyên ~K~ ~(2 \leq K \leq 50)~.

Dòng thứ hai chứa các số nguyên ~Z_1,...,Z_k~ cách nhau bởi khoảng trắng ~(1 \leq Z_1,...,Z_k \leq 50)~.

Dòng thứ ba chứa một biểu thức số học hoàn mỹ theo định dạng được mô tả. Một biểu thức số học bao gồm các kí tự ?, *, +, (, ), và có độ dài không vượt quá ~1\:000\:000~ kí tự.

Output

In ra giá trị lớn nhất có thể đạt được của biểu thức. Kết quả in ra được coi là chính xác nếu sai số tuyệt đối với đáp án không vượt quá ~10^{-3}~.

Sample 1

Input

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

Output

6.00000

Giải thích

Biểu thức ((3)+(3)) thõa mãn điều kiện của một biểu thức số học hoàn mỹ, và ta có thấy rằng không thể tìm ra biểu thức nào khác với giá trị lớn hơn 6.

Sample 2

Input

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

Output

6.00000

Giải thích

Giá trị lớn nhất có thể đạt được với biểu thức (((1)+(2))*(2)).

Sample 3

Input

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

Output

8.000000000

Giải thích

Giá trị lớn nhất có thể đạt được với biểu thức ((2)*(2)*(2)).