Kvalitetni

Μια ποιοτική αριθμητική έκφραση αποτελείται από αγκύλες, αριθμό και πράξεις πολλαπλασιασμού και πρόσθεσης.

Μια ποιοτική αριθμητική έκφραση ορίζεται αναδρομικά με τον ακόλουθο τρόπο:

• Μια έκφραση που αποτελείται από έναν μόνο θετικό πραγματικό αριθμό μικρότερο ή ίσο του ~Z_1~ είναι καλής ποιότητας.
  Μια τέτοια έκφραση έχει την εξής μορφή:

~(X)~

Για παράδειγμα, αν ~Z_1 = 5~, τότε το ~(4)~ είναι μια ποιοτική έκφραση.

• Εάν οι ~A_1,\;A_2,\;\ldots,\;A_k~ είναι ποιοτικές εκφράσεις τέτοιες ώστε ~2 \le k \le K~ και το άθροισμα αυτών των παραστάσεων είναι το πολύ ~Z_k~, τότε οι παρακάτω εκφράσεις είναι καλής ποιότητας:

~(A_1 + A_2 + \ldots + A_k)~
~(A_1 * A_2 * \ldots * A_k)~

Σας δίνεται μια ποιοτική αριθμητική έκφραση όπου οι αριθμοί αντικαθίστανται από ερωτηματικά.
Προσδιορίστε τη μέγιστη δυνατή τιμή που θα μπορούσε να έχει η παράσταση.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιο αριθμό ~K\;(2 \le K \le 50)~.
Η δεύτερη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~Z_1,\;\ldots,\;Z_k~, διαχωρισμένους με κενό ~(1 \le Z_1,\;\ldots,\;Z_K \le 50).~
Η τρίτη γραμμή εισόδου περιέχει μία ποιοτική αριθμητική έκφραση στην περιγραφόμενη μορφή.
Η αριθμητική έκφραση αποτελείται από: '?', '*', '+', '(', ')' και το μήκος της είναι ~1\,000\,000~ χαρακτήρες το πολύ.

Έξοδος

Πρέπει να τυπώσετε τη μέγιστη δυνατή τιμή της έκφρασης.
Μια λύση θεωρείται σωστή εάν η απόλυτη ή σχετική απόκλιση από την επίσημη λύση είναι μικρότερη από ~10^{-3}~​.

Παραδείγματα

input

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

output

6.00000

Επεξήγηση του 1ου παραδείγματος:

Η έκφραση ~((3)+(3))~ ικανοποιεί τις συνθήκες, επομένως είναι μια έκφραση ποιότητας και είναι εύκολο να ελέγξετε ότι το 6 είναι η μέγιστη τιμή.

input

3
253
(((?)+(?))*(?))

output

6.00000

Επεξήγηση του 2ου παραδείγματος:

Το μέγιστο επιτυγχάνεται, για παράδειγμα, για την έκφραση ~(((1)+(2))\ast(2))~.

input

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

output

8.000000000

Επεξήγηση του 3ου παραδείγματος:

Το μέγιστο επιτυγχάνεται, για παράδειγμα, για την έκφραση ~((2)*(2)*(2))~.