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
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<=(e);i++)
#define FORD(i,s,e) for(int i=(s);i>=(e);i--)
#define ALL(k) (k).begin(),(k).end()
#define e1 first 
#define e2 second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIP;
typedef pair<PLL,PLL> PPP;

const int MAXN=3000111;
const int MOVE=1000111;
const LL INF=(LL)1e16;

int tab[MAXN];
char ciag[MAXN];
int odw[MAXN];

int pier[MAXN];
int dp[MAXN];
vector<int> starts[MAXN];


LL wyn[MAXN];
LL w1[MAXN],w2[MAXN];
main(){
	int n;scanf("%d",&n);
	FOR(i,1,n)
		scanf("%d",&tab[i]);
	int m;scanf("%d",&m);
	scanf("%s",ciag);
	int skok=n%m;
	FOR(i,1,n)
		starts[(i-1)%m].PB(i);
	FOR(i0,0,m-1){
		if(odw[i0]) continue;
		vector<int> V;
		vector<int> V0;
		int v=i0;
		V.PB(-1);
		while(!odw[v]){
			V0.PB(v);
			V.PB(v);
			odw[v]=1;
			v=(v+skok)%m;
		}
		for(auto it:V0) V.PB(it);
		/*printf("%d::\n",i0);
		for(auto it:V) printf("%d ",it);
		puts("");*/
		int ii=0;
		for(auto it:V){
			if(it==-1) dp[ii]=0;
			else dp[ii]=dp[ii-1]+((ciag[it]=='W')?1:-1);
			//printf("%2d %2d %c %2d\n",ii,it,(it==-1)?'X':ciag[it],dp[ii]);
			ii++;
		}
		deque<int> D;
		int vs=V0.size();
		FORD(i,ii-1,1){
			//printf("A %2d %2d\n",i,dp[i]);
			pier[MOVE+dp[i]]=i;
			pier[MOVE+dp[i-1]]=i-1;
			while(!D.empty()&&D.back()>dp[i]) D.pop_back();
			D.PB(dp[i]);
			if(i>vs) continue;
			if(D.front()==dp[i+vs]) D.pop_front();
			LL suma=dp[i+vs-1]-dp[i-1];
			LL minim=D.front()-dp[i-1];
			//printf("%2d %2d %2d %2lld %2lld\n",i,dp[i-1],D.front(),minim,suma);
			int it=V[i];
			for(auto it1:starts[it]){
				int dl=tab[it1];
				//printf("\t%d %d:: ",it1,dl);
				if(suma>=0&&-minim<dl){
					//printf("XD %lld %lld %d\n",suma,minim,dl);
					wyn[it1]=INF;
					continue;
				}
				LL k=0;
				if(suma<0){
					k=max(0LL,(dl+minim))/(-suma);
					if((max((dl+minim),0LL))%(-suma)) k++;
				}
				//printf("%2d %2lld %2lld %2lld;; ",dl,minim,-suma,k);
				wyn[it1]+=k*(LL)V0.size();
				dl+=k*(LL)suma;
				//printf("%lld %d %d %d;; %d\n",wyn[it1],dl,dp[i-1],dp[i-1]-dl,pier[MOVE+dp[i-1]-dl]);
				wyn[it1]+=pier[MOVE+dp[i-1]-dl]-i;
			}
			//printf("%2d %2d\n",i+vs,dp[i+vs]);
		}
		FOR(i,0,vs+2) {
			pier[MOVE+dp[i]]=0;
			dp[i]=0;
		}
	}
	//FOR(i,1,n) printf("%d %lld\n",i,wyn[i]); puts("");
	w1[0]=wyn[1];
	FOR(i,1,n) w1[i]=min(w1[i-1],wyn[i]);
	w2[n+1]=wyn[n];
	FORD(i,n,1) w2[i]=min(w2[i+1],wyn[i]);
	if(w1[n]==INF) {puts("-1");return 0;}
	LL odp=((LL)n)*w1[n];
	FOR(i,1,n)
		if(w1[i]>w2[i+1]) odp=max(odp,i*(w2[i+1]+1)+(n-i)*w2[i+1]);
	printf("%lld\n",odp+1);
}