1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <algorithm>
using namespace std;
const long long inf=4200000000000000000LL;
int n,i,m,j,k,e,sum,diff,down,le,t,st[1000100],wt[1000100],a[1000100],b[1000100],c[1000100];
long long x,steps,r=inf;
char s[1000100];
bool u[1000100];
int main() {
  scanf("%d",&n);
  for (i=0; i<n; i++) scanf("%d",&a[i]);
  scanf("%d",&m);
  scanf("%s",s);
  for (i=0; i<m; i++) if (!u[i]) {
    t=1; st[1]=wt[1]=0;
    for (j=i, k=1; !u[j]; j=(j+m-n%m)%m, k++) {
      b[k]=j; u[j]=true;
      c[k]=c[k-1]+(s[j]=='W'?-1:1);
      for (; t>0 && st[t]>=c[k]; t--);
      st[++t]=c[k]; wt[t]=k;
    }
    sum=c[--k];
    for (le=j=1; j<=k; j++) {
      sum+=(s[b[j]]=='W'?-1:1);
      for (; t>0 && st[t]>=sum; t--);
      st[++t]=sum; wt[t]=k+j;
      for (le=min(le,t); wt[le]<=j; le++);
      diff=sum-c[j];
      down=t-le;
      for (e=b[j]; e<n; e+=m) {
        if (down>=a[e]) {
          steps=k+j-wt[t-a[e]]-1;
          r=min(r,steps*n+e+1);
        }
        if (diff<=0) continue;
        x=(a[e]-down+diff-1)/diff;
        a[e]-=diff*x;
        steps=k+j-wt[t-a[e]]-1;
        r=min(r,(steps+x*k)*n+e+1);
      }
    }
  }
  printf("%lld\n",r==inf?-1:r);
  return 0;
}