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
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<vector>
#define PII pair<int,int>
#define INF 2000000000000000000LL
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define LL long long
using namespace std;
int kasa[1000000];
PII gdzie[1000000];
LL wynik[1000000];
vector<int>chlopcy[1000000];
const int p1=1024*2048;
int drz[p1*2];
void insert(int x,int a){
	x+=p1-1;
	drz[x]=a;
	x=(x-1)/2;
	while(1){
		drz[x]=max(drz[2*x+1],drz[2*x+2]);
		if(x==0)return;
		x=(x-1)/2;
	}
}
int pos(int gran){
	int x=0;
	if(gran>drz[0])return -1;
	while(x<p1-1){
		if(drz[2*x+1]>=gran)x=2*x+1;
		else x=2*x+2;
	}
	return x-p1+1;
}
int maks(int a,int b){
	a+=p1-1;
	b+=p1-1;
	int res=max(drz[a],drz[b]);
	while((a-1)/2!=(b-1)/2){
		if(a%2==1)res=max(res,drz[a+1]);
		if(b%2==0)res=max(res,drz[b-1]);
		a=(a-1)/2;
		b=(b-1)/2;	
	}
	return res;
}
string gra;
vector<vector<int> >cykl;
int wart(char c){
	if(c=='W')return 1;
	else return -1;	
}
void licz(int x){
	int n=cykl[x].size();
	/*cout<<"licz\n";
	for(int i=0;i<n;i++)cout<<wart(gra[cykl[x][i]])<<" ";
	cout<<"\n";*/
	for(int i=0;i<2*n;i++)insert(i,-1000000000);
	insert(0,-wart(gra[cykl[x][0]]));
	for(int i=1;i<n;i++)insert(i,-wart(gra[cykl[x][i]])+drz[p1-2+i]);
	int poprawka=0,suma=drz[p1-1+n-1];
	for(int i=0;i<n;i++){
		int najw=maks(i,i+n-1)+poprawka,tury;
		/*cout<<"najw suma pop "<<najw<<" "<<suma<<" "<<poprawka<<"\n";
		for(int j=0;j<n;j++)cout<<drz[p1-1+i+j]<<" ";
		cout<<"\n";*/
		for(int j=0;j<chlopcy[cykl[x][i]].size();j++){
			tury=0;
			int kwota=kasa[chlopcy[cykl[x][i]][j]];
			//cout<<"kwota "<<kwota<<"\n";
			if(kwota>najw&&suma>0){
				tury=(kwota-najw+suma-1)/suma;
			}
			int granica=kwota-tury*suma;
			int p=pos(granica-poprawka);
			if(p!=-1)p-=i;
			if(p>=n)p=-1;
			//cout<<"p tury "<<p<<" "<<tury<<"\n";
			wynik[chlopcy[cykl[x][i]][j]]=((p==-1)?INF:((LL)tury*n+p));
			if(granica==0&&p!=-1)wynik[chlopcy[cykl[x][i]][j]]--;
			//cout<<wynik[chlopcy[cykl[x][i]][j]]<<"\n";
		}
		poprawka+=wart(gra[cykl[x][i]]);
		insert(i,-1000000000);
		insert(i+n,drz[p1-1+i+n-1]-wart(gra[cykl[x][i]]));
	}
}
int m,nn;
LL koniec(int nr){
	if(wynik[nr]==INF)return INF;
	return (LL)nr+1+wynik[nr]*nn;
}
bool odw[1000000];
main(){
	ios_base::sync_with_stdio(0);
	int n;	
	cin>>n;
	nn=n;
	for(int i=0;i<n;i++)cin>>kasa[i];
	cin>>m;
	for(int i=0;i<n;i++)chlopcy[i%m].pb(i);
	cin>>gra;
	for(int i=0;i<m;i++){
		if(odw[i])continue;
		vector<int>tmp;
		gdzie[i]=mp(cykl.size(),tmp.size());
		tmp.pb(i);
		odw[i]=1;
		int x=(i+n)%m;
		while(x!=i){
			gdzie[x]=mp(cykl.size(),tmp.size());
			tmp.pb(x);
			odw[x]=1;
			x=(x+n)%m;	
		}
		cykl.pb(tmp);
	}
	for(int i=0;i<cykl.size();i++)licz(i);
	LL res=INF;
	for(int i=0;i<n;i++){
		LL akt=koniec(i);
		if(res>akt)res=akt;	
	}
	if(res==INF)cout<<"-1\n";
	else cout<<res<<"\n";
}