양질의 수식

시간 제한1초메모리 제한64 MB

요약

괄호식의 물음표 자리에 값을 채워 각 결합의 합 제한을 지키면서 전체 값을 최대로 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, 백트래킹
정답자: 아직 제출이 없습니다

문제

양질의 수식은 괄호, 수, 곱셈, 덧셈으로 이루어진다.

양질의 수식은 다음과 같이 재귀적으로 정의한다.

$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 + \cdots + A_k) \qquad (A_1 * A_2 * \cdots * A_k)$

양질의 수식에서 수를 모두 물음표로 바꾼 결과가 주어진다. 원래 수식이 가질 수 있었던 값의 최댓값을 구하라.

입력

첫째 줄에 정수 $K$ 가 주어진다. ( $2 \le K \le 50$ )

둘째 줄에 정수 $Z_1, \ldots, Z_K$ 가 공백으로 구분되어 주어진다. ( $1 \le Z_i \le 50$ )

셋째 줄에 위에서 설명한 형식의 양질의 수식이 하나 주어진다. 수식은 ?, *, +, (, ) 다섯 문자로만 이루어지고, 길이는 1,000,000 이하이다.

출력

수식이 가질 수 있는 값의 최댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다.

힌트

$K = 2$ , $Z_1 = 10$ , $Z_2 = 6$ 이고 수식이 ((?)+(?))인 경우를 보자. 두 물음표를 모두 3으로 바꾸면 두 부분식의 값의 합이 $6$ 이라 $Z_2$ 이하이므로 ((3)+(3))은 양질의 수식이고, 그 값은 $6$ 이다. 이보다 큰 값은 만들 수 없다.

예제3

예제 1
입력
```
2
10 6
((?)+(?))
```
예상 출력
```
6.000000
```
예제 2
입력
```
3
2 5 3
(((?)+(?))*(?))
```
예상 출력
```
6.000000
```
예제 3
입력
```
3
2 10 6
((?)*(?)*(?))
```
예상 출력
```
8.000000
```