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
#include <bits/stdc++.h>
using namespace std;

long long k[1000007];
char cykl[1000007];
bool odw[2000007];
long long a[2000007];
long long b[2000007];
long long n[2000007];
pair<int,int> do_ktorego[2000007];
long long cykle[20000007];
long long od_ktorego[2000007];
long long minimum_na_cyklu[2000007];
int main()
{
	long long N,M;
	scanf("%lld",&N);
	for (long long i = 0;i < N;i++)
	{
		scanf("%lld",&k[i]);
	}
	scanf("%lld",&M);
	scanf("%s",cykl);
	long long liczba_cykli = __gcd(N,M);
	long long dlugosc_cykli = M/__gcd(N,M);
	long long il;
	int cmmm = 0;
	for (int i = 0;i < M;i++)
	{
		if (!odw[i])
		{
			il = 0;
			for (int s = 0,w = i;s < dlugosc_cykli*2;s++,w=(w+N)%M)
			{
				odw[w] = true;
				od_ktorego[cmmm*dlugosc_cykli+s] = w;
				do_ktorego[w] = make_pair(cmmm,s%M);
				if (cykl[w] == 'W')
					il++;
				else
					il--;
				cykle[cmmm*dlugosc_cykli+s] = il;
			}
			cmmm++;
		}
	}
	for (long long i = 0;i < liczba_cykli;i++)
	{
		minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli] = cykle[i*dlugosc_cykli+dlugosc_cykli];
		minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli-1] = cykle[i*dlugosc_cykli+dlugosc_cykli-1];
		for (long long w = dlugosc_cykli-2;w >= 0;w--)
		{
			minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w+1],cykle[i*dlugosc_cykli+w]);
		}
		for (long long w = dlugosc_cykli+1;w < dlugosc_cykli*2;w++)
		{
			minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]);
		}
	}
	for (long long i = 0;i < liczba_cykli;i++)
	{
		for (long long w = 0;w < dlugosc_cykli;w++)
		{	
			a[od_ktorego[i*dlugosc_cykli+w]] = cykle[i*dlugosc_cykli+dlugosc_cykli-1];
			b[od_ktorego[i*dlugosc_cykli+w]] = min(minimum_na_cyklu[i*dlugosc_cykli+w],minimum_na_cyklu[i*dlugosc_cykli+w+dlugosc_cykli-1])-cykle[i*dlugosc_cykli+w-1];
		}
		b[od_ktorego[i*dlugosc_cykli+0]] = minimum_na_cyklu[i*dlugosc_cykli+0];
	}
	long long minimum = 100000000007;
	for (long long i = 0;i < N;i++)
	{
		if (k[i] <= -b[i%M])
			n[i] = 0;
		else if (a[i%M] < 0)
			n[i] = (k[i]+b[i%M]-a[i%M]-1)/(-a[i%M]);
		else
			n[i] = -1;
		if (n[i] != -1)
			minimum = min(minimum,n[i]);
	}
	for (long long i = 0;i < liczba_cykli;i++)
	{
		minimum_na_cyklu[i*dlugosc_cykli+0] = cykle[i*dlugosc_cykli+0];
		for (long long w = 1;w < dlugosc_cykli*2;w++)
			minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]);
	}
	if (minimum == 100000000007)
	{
		printf("-1");
		return 0;
	}
	long long pocz,sr,kon;
	long long kt;
	long long f;
	long long megamini = 1000000000007;
	long long odjo;
	long long pp;
	for (int i = 0;i < N;i++)
	{
		if (n[i] == minimum)
		{
			kt = do_ktorego[i].first;
			pocz = do_ktorego[i].second-1;
			kon = pocz+dlugosc_cykli+1;
			odjo = a[i]*n[i];
			pp = pocz;
			if (pocz != -1)
				f = cykle[kt*dlugosc_cykli+pocz];
			else
				f = 0;
			while (pocz+1 != kon)
			{
				sr = (pocz+kon)/2;
				if (-(minimum_na_cyklu[kt*dlugosc_cykli+sr]-f) >= k[i]+odjo)
					kon = sr;
				else
					pocz = sr;
			}
			megamini = min(megamini,((kon-pp-1)*N)+i+1);
		}
	}
	printf("%lld",(minimum*N*dlugosc_cykli)+megamini);
	
	return 0;
}