Dungeon

Albert designed a dungeon game that one person can play alone. The game takes place on a one-dimensional line. The hero moves through rooms in order, from room $0$ to room $N$. The hero starts in room $0$ with initial health $X$. (Albert decides this value later.)

Each room from $1$ to $N$ has one monster, and each monster guards one magic scroll. Fighting the monster in room $i$ reduces the hero's health by $D_i > 0$. If the health drops to $0$ or below, the hero loses. After defeating a monster, the hero uses the scroll in that room to raise health. Each scroll is either an addition scroll or a multiplication scroll, and it has a positive integer $R_i$ written on it. The string $S$ is given as input, and $S_i$ gives the type of the scroll in room $i$.

• If the scroll in room $i$ is an addition scroll, $S_i$ is '+', and using it raises the hero's health by $R_i$.
• If the scroll in room $i$ is a multiplication scroll, $S_i$ is '*', and using it multiplies the hero's health by $R_i$.

Albert's goal is to start with health $X$ in room $0$, move through each room in order, and defeat every monster up to room $N$. The scroll from room $i$ must be used right away.

For example, take $N = 4$, $D = [5, 10, 15, 20]$, $S =$ '+*++', and $R = [2, 3, 4, 5]$.

• If $X = 10$, room 1 leaves health at 5, and the +2 scroll brings it to 7. In room 2, health becomes $-3$, so the hero loses.
• If $X = 22$, room 1 leaves 17, and the scroll brings it to 19. Room 2 leaves 9, and the $\times 3$ scroll brings it to 27. Room 3 leaves 12, and the +4 scroll brings it to 16. Room 4 leaves $-4$, so the hero loses.
• If $X = 30$, room 1 leaves 25, and the scroll brings it to 27. Room 2 leaves 17, and the scroll brings it to 51. Room 3 leaves 36, and the scroll brings it to 40. Room 4 leaves 20, and the scroll brings it to 25. The hero defeats every monster.

In this example, the hero cannot defeat all monsters with initial health below 24. With initial health 24 or more, the hero can defeat all monsters.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$. The second line contains $N$ positive integers $D_1, D_2, \dots, D_N$, separated by spaces. The third line contains a string $S$ of length $N$ with no spaces, where each character is '+' or '*'. The fourth line contains $N$ positive integers $R_1, R_2, \dots, R_N$, separated by spaces.

Print the answer for each test case on its own line.

• $1 \le T \le 10$
• $1 \le N \le 10^5$
• For every $i$ with $1 \le i \le N$:
  • $1 \le R_i, D_i \le 10^8$
  • $S_i$ is '+' or '*'.
• The answer for each test case is at most $2^{63}-1$.