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


long long Sum[40][1000000];
int Lo[40][1000000];

char A[1000001];

int C[1000000];

int N, M;


void load() {
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        scanf("%d", &C[i]);
    
    scanf("%d%s", &M, A);
}

void populate_tables() {
    for (int i=0; i<M; i++)
        Lo[0][i] = Sum[0][i] = (A[i]=='W') ? +1 : -1;
    
    int d = N % M;
    for (int e=1; e<40; e++, d=(d+d)%M) {
        for (int i=0; i<M; i++) {
            int j = (i+d)%M;
            Sum[e][i] = Sum[e-1][i] + Sum[e-1][j];
            long long lol = Sum[e-1][i]+Lo[e-1][j];
            if (lol < -10000000)
                Lo[e][i] = -10000000;
            else
                Lo[e][i] = min(Lo[e-1][i], int(lol));
        }
    }
}


long long game_length(int b, long long money) {
    int s = b % M;
    long long distance = 0;
    long long pace = N;
    int e = 0;

    while (e < 40) {
        if (money > 2000000) return numeric_limits<long long>::max();
        if (money + Lo[e][s] > 0) {
            distance += pace;
            money += Sum[e][s];
            s = (s+pace) % M;
        }
        else {
            break;
        }

        pace *= 2, e++;
    }

    if (e == 40)
        return numeric_limits<long long>::max();

    pace /= 2, e--;

    while (e>=0) {
        if (money > 2000000) return numeric_limits<long long>::max();
        if (money + Lo[e][s] > 0) {
            distance += pace;
            money += Sum[e][s];
            s = (s+pace) % M;
        }
        pace /= 2, e--;
    }

    return b + distance + 1;
}


void run() {
    long long result = numeric_limits<long long>::max();
    for (int i=0; i<N; i++)
        result = min(result, game_length(i, C[i]));

    if (result == numeric_limits<long long>::max())
        printf("-1\n");
    else
        printf("%lld\n", result);
}


int main() {
    load();

    populate_tables();

    run();

    return 0;
}