던전 | cho.sh

문제

Albert는 혼자 할 수 있는 던전 게임을 고안했다. 이 게임은 1차원상에서 진행되며, $0$ 번 방 부터 $N$ 번 방까지 순차적으로 "용사"를 움직이며 진행한다. $0$ 번 방에는 용사가 있으며 용사의 처음 체력을 $X$ 라 하자 (이 값은 Albert가 추후에 정하는 값이다).

$1$ 번 부터 $N$ 번 방까지 각 방에는 몬스터가 하나 있고 몬스터는 마법 주문서 하나를 지키고 있다. $i$ 번째 방의 몬스터와 싸우면 용사의 체력은 $D\_i \gt 0$ 만큼 깎이는데, 만약 용사의 체력이 0이하가 되면 용사가 패배한다. 몬스터를 물리친 이후 그가 지키고 있던 주문서를 이용하면 체력을 올릴 수 있다. $i$ 번째 방의 주문서는 "덧셈주문서" 이거나 "곱셈주문서"인데, 양의 정수 $R\_i$ 가 적혀 있다. 편의상 문자열 $S$ 가 입력으로 주어지며, $S\_i$ 가 $i$ 번째 주문서의 종류를 나타낸다고 하자.

$i$ 번째 주문서가 덧셈주문서라면 $S\_i$ 가 '+' 이고, 이 주문서를 사용하면 용사의 체력이 $R\_i$ 만큼 올라간다.
$i$ 번째 주문서가 곱셈주문서라면 $S\_i$ 가 '*' 이고, 이 주문서를 사용하면 용사의 체력이 $R\_i$ 배로 올라간다.

Albert는 용사의 처음 체력이 $X$ 인 상태로 시작하여 $0$ 번 방에서 각 방을 순서대로 지나 $N$ 번 방의 몬스터까지 물리치는 것이 목표이다. 이 때 $i$ 번째 방에서 몬스터를 물리치고 얻은 주문서는 반드시 즉시 사용해야한다.

예를 들어 $N = 4$ , $D = \[5, 10, 15, 20]$ , $S =$ "+*++", $R = \[2, 3, 4, 5]$ 인 경우를 생각해보자.

처음 용사의 체력이 $X = 10$ 이라면:
- 1번 방: 몬스터와 싸운 후 체력이 $D\_1 = 5$ 만큼 깎여 5가 된다. 이후 주문서를 이용하여 +2 만큼 체력을 올려 7이 된다.
- 2번 방: 체력이 $D\_2 = 10$ 만큼 깎여 -3이 되므로 용사가 패배한다.
처음 용사의 체력이 $X = 22$ 이라면:
- 1번 방: 몬스터와 싸운 후 체력이 17이 되고, 이후 주문서를 이용하여 체력이 19가 된다.
- 2번 방: 몬스터와 싸운 후 체력이 9가 되고, 주문서를 이용하여 체력이 3배로 올라 27이 된다.
- 3번 방: 몬스터와 싸운 후 체력이 12가 되고, 주문서를 이용하여 체력이 16이 된다.
- 4번 방: 몬스터와 싸운 후 체력이 -4가 되어 용사가 패배한다.
처음 용사의 체력이 $X$ = 30이라면:
- 1번 방: 몬스터와 싸운 후 체력이 25가 되고, 이후 주문서를 이용하여 체력이 27이 된다.
- 2번 방: 몬스터와 싸운 후 체력이 17이 되고, 주문서를 이용하여 체력이 3배로 올라 51이 된다.
- 3번 방: 몬스터와 싸운 후 체력이 36이 되고, 주문서를 이용하여 체력이 40이 된다.
- 4번 방: 몬스터와 싸운 후 체력이 20이 되고, 주문서를 이용하여 체력이 25가 된다.

위의 예제의 경우 처음 용사의 체력이 24미만이면 모든 몬스터를 물리칠 수 없지만 24이상이면 모든 몬스터를 물리칠 수 있음을 보일 수 있다.

입력으로 던전에 대한 정보인 $N, D, S, R$ 이 주어졌을 때, 모든 몬스터를 물리치기 위해 필요한 용사의 처음 체력의 최솟값을 구해보자.

입력

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$ 이 주어진다. 둘째 줄에는 $N$ 개의 양의 정수가 공백으로 구분되어 주어지는데 이는 $D\_1, D\_2, \dots, D\_N$ 을 나타낸다. 셋째 줄에는 길이 $N$ 인 문자열 $S$ 가 공백없이 주어지는데 이는 각 주문서의 보상 종류는 타나낸다. 각 문자는 '+' 혹은 '*'이다. 넷째 줄에는 $N$ 개의 양의 정수가 공백으로 구분되어 주어지는 이는 $R\_1, R\_2, \dots, R\_N$ 을 나타낸다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다.

제한

$1 \le T \le 10$
$1 \le N \le 10^5$
$1 \le i \le N$ 인 $i$ 에 대하여:
- $1 \le R\_i, D\_i \le 10^8$
- $S\_i$ = '+' 혹은 $S\_i$ = '*' (따옴표 제외)
각 테스트 케이스의 정답은 $2^{63}-1$ 이하이다.