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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ULL;
const int N=1000*1000+7;
const int OFFSET = 2*N;
int M=1;
const ULL MAX = ULL(1000*1000*1000)*ULL(1000*1000*1000);

char buf[N];
int money[N];
int wins[N];
int prizes[2*N];
int tree[1024*1024*4+7];

vector<int>place_with_value[4*N];

ULL wyn = MAX;

int gcd (int a, int b)
{
  while (b!=0)
  {
    int tmp = a%b;
    a = b;
    b = tmp;
  }
  return a;
  if (b==0)
    return a;
}

int get_min (int p, int k)
{
  int w;
  p+=M;
  k+=M;
  w = min (tree[p], tree[k]);
  while (p/2!=k/2)
  {
    if (!(p&1))
      w = min (w, tree[p+1]);
    if (k&1)
      w = min (w, tree[k-1]);
    p/=2;
    k/=2;
  }
  return w;
}

int main ()
{
	ULL n, m;
  scanf("%lld", &n);
  for (int i=0; i<n; i++)
    scanf("%d", &money[i]);
  scanf("%lld", &m);
  scanf("%s", buf);
  for (int i=0; i<m; i++)
    wins[i] = (buf[i] == 'W' ? 1 : -1);

  ULL group_size = gcd(n, m);
  ULL small_n = n/group_size;
  ULL small_m = m/group_size;

  while (M <= small_n+small_m)
    M<<=1;

  for (int g=0; g<group_size; g++)
  {
    //rozwinięte ceny
    prizes[0] = 0;
    for (int i=0; i<2*M; i++)
      tree[i] = 1000*1000*1000;
    for (int i=1; i<=small_n+small_m; i++)
      tree[i+M] = prizes[i] = prizes[i-1] + wins[(((i-1)*small_n)%small_m) * group_size + g];

    for (int i=M-1; i>0; i--)
      tree[i] = min (tree[i*2], tree[i*2+1]);

    int sum = prizes[small_m];

    for (int j=-small_m-small_n; j<=small_m+small_n; j++)
      place_with_value[j+OFFSET].clear();

    for (int i=1; i<=small_n+small_m; i++)
      place_with_value[prizes[i]+OFFSET].push_back(i);

    for (int i=0; i<small_n; i++) //normalnej kolejności, chcemy znać indeks rozwinięcia
    {
      int w = i * group_size + g;
      int k = (i*small_n)%small_m;
      int value = money[w];

      int min_value = get_min(k+1, k+small_m)-prizes[k];

      if (min_value+value > 0 && sum>=0)
        continue;

      ULL wyn_t = 0;

      if (min_value + value > 0)
      {
        wyn_t = (value+min_value-1-sum)/(-sum);
        value += wyn_t*sum;
        wyn_t *= small_m;
      }

      wyn_t += *upper_bound(place_with_value[OFFSET + prizes[k]-value].begin(), place_with_value[OFFSET + prizes[k]-value].end(), k) - k;

/*      for (auto e : place_with_value[OFFSET + prizes[k]-value])
        if (e > k)
        {
          wyn_t += e-k;
          break;
        }*/

      wyn = min (wyn, (wyn_t-1) * n + w + 1);
    }
  }

  printf("%lld\n", wyn == MAX ? -1 : wyn);
	return 0;
}