도박

Bajtek과 친구들이 몰래 카지노에 들어갔다. 소년들은 용돈을 빨리 불리려고 "외팔이 강도"라고 불리는 슬롯머신 앞에 모였다. 공정하게 하려고 소년들은 순서대로 게임을 한다. 게임이 끝나면 방금 한 사람은 줄의 맨 뒤로 간다.

게임 방법은 간단하다. 플레이어는 매번 1 바이탈라를 걸고 레버를 당겨 이겼는지 확인한다. 이기면 기계가 2 바이탈라를 내준다. 지면 아무 일도 일어나지 않는다. 즉 한 게임에서 1 바이탈라를 얻거나 잃는다.

소년들은 카지노 주인이 숨겨진 카메라로 지켜보고 있다는 사실을 모른다. 주인은 기계가 길이 m인 주기로 동작한다는 것을 안다. 따라서 m번째마다 결과가 항상 같다. 주인은 주기의 정확한 모양도 알고 있다.

주인은 보안요원을 부를지 고민한다. 소년 중 한 명이 저축을 모두 잃으면 그 소년이 카지노를 떠나고, 친구들도 연대해서 함께 나갈 것이라고 주인은 짐작한다. (주인도 한때는 어린 소년이었다.) 그는 그런 일이 언젠가 일어나는지, 일어난다면 얼마나 빨리 일어나는지 알고 싶어 한다. 소년들이 곧 스스로 나간다면 보안요원을 부를 필요가 없을 수도 있다. 그 사이에 소년들 저축의 대부분이 카지노 수익이 된다면 더욱 그렇다.

첫 줄에 정수 n (1 ≤ n ≤ 1 000 000)이 주어진다. 카지노에 온 소년의 수이며 Bajtek도 포함한다.

둘째 줄에는 정수 n개가 주어진다. 소년들이 기계 앞에 선 순서대로 각자의 저축액이다. 각 값은 $[1, 10^6]$ 범위에 있다.

셋째 줄에 기계 주기의 길이 m (1 ≤ m ≤ 1 000 000)이 주어진다.

넷째 줄에는 길이 m인 문자열이 주어진다. i번째 문자가 W이면 주기의 i번째 게임에서 플레이어가 이기고, P이면 진다. 문자열에는 W가 적어도 하나 있다.

소년들이 게임을 한 총 횟수를 한 줄에 출력한다. 이는 소년 중 한 명이 저축을 모두 잃을 때까지의 횟수이다. 그런 일이 일어나지 않으면 -1을 출력한다.