Bajtek and his friends have snuck into a casino. The boys lined up at a slot machine with the intention of quickly multiplying their pocket money savings. To be fair, the boys decided to play in turns: after finishing a game, each boy moves to the end of the queue. The game on the machine chosen by the boys is trivial. The player always bets one "bajtalar" and pulls the lever to see if they have won. If they win, the machine pays out two bajtalars; otherwise, nothing happens. In other words, in a single game, one can gain or lose one bajtalar.

Our underage gamblers do not know that the casino owner is watching all their actions from a hidden camera. He knows that the machine operates in a cycle of length $m$, meaning the result of every $m$-th game is always the same. Moreover, the casino owner knows the exact form of the machine's cycle.

Now the owner is wondering whether to call casino security. He suspects that if any of the boys loses all their savings on the machine, that boy will leave the casino, and his friends will leave with him in solidarity (he was once their age, too!). The owner would like to check if this will ever happen, and if so, how soon. After all, if the boys leave on their own soon, it might not be worth calling security. Especially if it turns out that in the meantime, most of their savings will increase the casino's budget...

Input

The first line of input contains a single integer $n$ ($1 \le n \le 1\,000\,000$) representing the number of friends who came to the casino (including Bajtek). The second line contains $n$ integers in the range $[1, 10^6]$, representing the savings of the boys in the same order as they lined up at the machine.

The third line contains a single integer $m$ ($1 \le m \le 1\,000\,000$) representing the length of the machine's operation cycle. The fourth line contains a string of $m$ characters representing the machine's operation cycle: if the $i$-th character of the string is 'W', the player wins the $i$-th game of the cycle, and if the character is 'P', the player loses the $i$-th game. The string contains at least one 'W'.

Output

Your program should output a single line containing one integer representing the total number of games the boys will play until one of them loses all their pocket money savings. If this moment never occurs, your program should output $-1$.

Examples

Input 1

4
2 3 2 1
3
WPP

Output 1

12