던전

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$ 이하이다.