#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
const int N = 1005;
const int MAXN = (1 << 21) + 5;
const LD PI = acosl(-1.0);

char s[4][N];
int n, m[N], ok1[MAXN], ok2[MAXN], cnt[MAXN];
LL sx[MAXN], sy[MAXN];

struct comp {
    LD r, i;
    comp() {}
    comp(LD _r, LD _i): r(_r), i(_i) {}
    friend comp operator + (comp a, comp b) {
        return comp(a.r + b.r, a.i + b.i);
    }
    friend comp operator - (comp a, comp b) {
        return comp(a.r - b.r, a.i - b.i);
    }
    friend comp operator * (comp a, comp b) {
        return comp(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
    }
    friend comp operator / (comp a, LD b) {
        return comp(a.r / b, a.i / b);
    }
};

int len, rev[MAXN];
comp w[MAXN], F[MAXN], G[MAXN];

void FFT_init(int m) {
    int bit = -1;
    for (len = 1; len < m; len <<= 1) ++bit;
    for (int i = 0; i < len; ++i) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    for (int i = 1; i < len; i <<= 1) {
        comp wn(cos(PI / i), sin(PI / i)), wnk(1, 0);
        for (int k = 0; k < i; ++k) {
            w[i + k] = wnk;
            wnk = wnk * wn;
        }
    }
}

void DFT(comp *a) {
    for (int i = 0; i < len; ++i) {
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < len; i <<= 1) {
        for (int j = 0; j < len; j += (i << 1)) {
            for (int k = 0; k < i; ++k) {
                comp x = a[j + k], y = w[i + k] * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }
}

void IDFT(comp *a) {
    DFT(a);
    reverse(a + 1, a + len);
    for (int i = 0; i < len; ++i) {
        a[i] = a[i] / len;
    }
}

void Exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1; y = 0;
        return;
    }
    Exgcd(b, a % b, y, x);
    y -= (a / b) * x;
}

inline LL Findl(LL L, LL x, LL d) { //find smallest i s.t. x + i*d >= L
    return -(x - L) / d;
}

inline LL Findr(LL R, LL x, LL d) { //find largest i s.t. x + i*d <= R
    return (R - x) / d;
}

void solve() {
    scanf("%d", &n);
    for (int i = 0; i < 4; ++i) {
        scanf("%s", s[i]);
        m[i] = strlen(s[i]);
    }
    int lcm1 = m[0] * m[1] / __gcd(m[0], m[1]);
    for (int i = 0; i < lcm1; ++i) {
        int i0 = i % m[0], i1 = i % m[1];
        ok1[i] = (s[0][i0] == 'T' && s[1][i1] == 'T');
    }
    int lcm2 = m[2] * m[3] / __gcd(m[2], m[3]);
    for (int i = 0; i < lcm2; ++i) {
        int i2 = i % m[2], i3 = i % m[3];
        ok2[i] = (s[2][i2] == 'P' && s[3][i3] == 'C');
    }
    LL d = __gcd(lcm1, lcm2);
    LL lcm = 1LL * lcm1 * lcm2 / __gcd(lcm1, lcm2);

    FFT_init(lcm1 + lcm2);
    for (int i = 0; i < lcm1; ++i) {
        F[lcm1 - i] = comp(ok1[i], 0);
    }
    for (int i = 0; i < lcm2; ++i) {
        G[i] = comp(ok2[i], 0);
    }
    DFT(F); DFT(G);
    for (int i = 0; i < len; ++i) {
        F[i] = F[i] * G[i];
    }
    IDFT(F);

    LL tot = 0, x, y;
    LL dif = lcm2 / d;
    Exgcd(lcm1, lcm2, x, y);
    for (int i = 0; i < len; ++i) {
        cnt[i] = (int)(F[i].r + .5);
        if (!cnt[i]) continue;
        if ((i - lcm1) % d) continue;
        sx[i] = x * (i - lcm1) / d;
        sy[i] = y * (lcm1 - i) / d;
        LL xl = Findl(0, sx[i], dif), xr = Findr(lcm / lcm1 - 1, sx[i], dif);
        LL yl = Findl(0, sy[i], dif), yr = Findr(lcm / lcm2 - 1, sy[i], dif);
        tot += max(0LL, min(xr, yr) - max(xl, yl) + 1) * cnt[i];
    }

    if (tot == 0) {
        puts("-1");
        return;
    }
    LL ans = 0;
    if (n > tot) {
        ans = (n - 1) / tot * lcm;
        n -= (n - 1) / tot * tot;
    }
    LL L = 0, R = lcm - 1, P = 0;
    while (L <= R) {
        LL M = (L + R) >> 1;
        LL ret = 0;
        LL lim1 = (M + 1) / lcm1, lim2 = (M + 1) / lcm2;
        for (int i = 0; i < len; ++i) {
            if (!cnt[i]) continue;
            if ((i - lcm1) % d) continue;
            LL xl = Findl(0, sx[i], dif), xr = Findr(lim1, sx[i], dif);
            LL yl = Findl(0, sy[i], dif), yr = Findr(lim2, sy[i], dif);
            tot += max(0LL, min(xr, yr) - max(xl, yl) + 1) * cnt[i];
        }
        for (int i = min(lim1 * lcm1, lim2 * lcm2); i <= M; ++i) {
            ret += (ok1[i % lcm1] && ok2[i % lcm2]);
        }
        if (ret >= n) {
            P = M;
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    printf("%lld\n", ans + P + 1);
}

int main() {
    solve();
    return 0;
}