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
#include <stdint.h>
#include <limits>
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;


int gcd(int const &a, int const &b) {
  return b ? gcd(b, a % b) : a;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n;
  cin >> n;
  
  vector<int> A(n);
  for(int i = 0; i < n; ++i) cin >> A[i];
  
  int l;
  string S;
  cin >> l >> S;
  
  int q = n % l;
  int g = gcd(l, n);
  int c = l / g;
  
  vector< vector<int> > OS(g);
  vector< vector< pair<int, int> > > MS(g);
  vector< map< int, vector<int> > > BV(g);
  for(int o = 0; o < g; ++o) {
    OS[o].resize(2 * c, 0);
    MS[o].resize(2 * c);
    
    OS[o][0] = (S[o % l] == 'W' ? 1 : -1);
    
    for(int j = 1; j < 2 * c; ++j) {
      OS[o][j] = OS[o][j - 1] + (S[(o + q * int64_t(j)) % l] == 'W' ? 1 : -1);
    }
    
    set< pair<int, int> > SS;
    for(int j = 0; j < 2 * c; ++j) {
      SS.insert(make_pair(OS[o][j], j));
      while(j - SS.begin()->second >= c) SS.erase(SS.begin());
      MS[o][j] = *SS.begin();
    }
    
    for(int j = 0; j < 2 * c; ++j) {
      if(BV[o].find(OS[o][j]) == BV[o].end()) BV[o][OS[o][j]] = vector<int>();
      BV[o][OS[o][j]].push_back(j);
    }
  }
  
  vector<int> Z2J(c);
  for(int j = 0; j < c; ++j) Z2J[((q * int64_t(j)) % l) / g] = j;
  
  int64_t result = numeric_limits<int64_t>::max();
  
  for(int i = 0; i < n; ++i) {
    int o  = i % g;
    int z0 = (i / g) % c;
    int j0 = Z2J[z0];
    int j1 = j0 + c;
    int p  = (j0 == 0 ? 0 : OS[o][j0 - 1]);
    
    int mv = MS[o][j1 - 1].first - p;
    
    int b = -(OS[o][j1-1] - p);
    if(b <= 0 and A[i] + mv > 0) continue;
    
    int full = 0;
    if(b > 0) full = (A[i] + mv + b - 1) / b;
    if(full < 0) full = 0;
    if(A[i] + mv <= 0) full = 0;
    
    int mNeed = A[i] - full * b;
    int mPoint = p - mNeed;
    int mSteps = 1 + *lower_bound(BV[o][mPoint].begin(), BV[o][mPoint].end(), j0) - j0;
    
    int64_t steps = full * int64_t(c) + mSteps;
    
    int64_t gSteps = 1 + i + (steps - 1) * int64_t(n);
    
    result = min(result, gSteps);
  }
  
  if(result == numeric_limits<int64_t>::max()) result = -1;
  
  cout << result << '\n';
  
  return 0;
}