#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 1e5 + 100, inf = 1e9 + 100;

ll lcm(ll a,ll b) {
    return a/gcd(a,b)*b;
}

namespace fft {
    using dbl = double;  // works for max value (max(a)*max(b)*n) up to 1e14 (multiply_mod with n up to 1e5)
// using dbl = long double;  // works for max value (max(a)*max(b)*n) up to 1e17
    const dbl PI = acosl(-1.0l);

    struct Complex {
        dbl x, y;
        Complex(dbl x = 0, dbl y = 0) : x(x), y(y) {}
        Complex conj() const {
            return Complex(x, -y);
        }
    };

    Complex  operator *  (const Complex &a, const Complex &b) { return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
    void	 operator /= (	  Complex &a, int n)			{ a.x /= n; a.y /= n; }
    Complex  operator /  (const Complex &a, int n)			{ return Complex(a.x / n, a.y / n); }
    Complex  operator +  (const Complex &a, const Complex &b) { return Complex(a.x + b.x, a.y + b.y); }
    Complex  operator -  (const Complex &a, const Complex &b) { return Complex(a.x - b.x, a.y - b.y); }

    string   to_string   (			const Complex &x) { return (string)"(" + std::to_string(x.x) + ", " + std::to_string(x.y) + ")"; };
    ostream& operator << (ostream &o, const Complex &x) { return o << to_string(x); }

    vector<Complex> buf1;
    vector<Complex> buf2;

    vector<Complex> w = {1, 1};
    vector<int> reversed = {0};

    void update_n(int n) {
        assert((n & (n - 1)) == 0);
        int cur = reversed.size();
        if (n <= cur) return;
        reversed.resize(n);
        w.resize(n + 1);
        while (cur < n) {
            for (int i = 0; i < cur; ++i)
                reversed[i] <<= 1;
            for (int i = cur; i < (cur << 1); ++i)
                reversed[i] = reversed[i - cur] ^ 1;
            for (int i = (cur << 1) - 2; i > 0; i -= 2)
                w[i] = w[i / 2];
            for (int i = 1; i < (cur << 1); i += 2)
                w[i] = Complex(cos(PI * i / cur), sin(PI * i / cur));
            cur *= 2;
        }
        w.back() = 1;
    }

    void fft_internal(vector<Complex> &v, int from, int n, bool inv) {
        update_n(n);
        int N = reversed.size();

        int d = __lg(N) - __lg(n);

        for (int i = 1; i < n; ++i)
            if (i < (reversed[i] >> d))
                swap(v[from + i], v[from + (reversed[i] >> d)]);

        for (int ln = 1; ln < n; ln <<= 1) {
            int step = (inv ? -N : N) / (ln * 2);
            for (int i = 0; i < n; i += (ln << 1)) {
                int ind = (inv ? N : 0);
                for (int j = 0; j < ln; ++j) {
                    Complex y = v[from + i + j + ln] * w[ind];
                    ind += step;
                    v[from + i + j + ln] = v[from + i + j] - y;
                    v[from + i + j]	  = v[from + i + j] + y;
                }
            }
        }

        if (inv)
            for (int i = 0; i < n; ++i)
                v[from + i] /= n;
    }

// only if you need this
    vector<Complex> fft(const vector<int> &v, int n = -1) {
        if (n == -1) {
            n = 1;
            while (n < v.size()) n <<= 1;
        }
        assert(v.size() <= n);
        buf1.assign(n, {0, 0});
        for (int i = 0; i < v.size(); ++i)
            buf1[i].x = v[i];
        fft_internal(buf1, 0, n, false);
        return vector<Complex>(buf1.begin(), buf1.end());
    }

// only if you need this
    vector<long long> fft(const vector<Complex> &v) {
        assert(!v.empty() && (v.size() & (v.size() - 1)) == 0);
        buf1.resize(v.size());
        for (int i = 0; i < v.size(); ++i)
            buf1[i] = v[i];
        fft_internal(buf1, 0, buf1.size(), true);
        vector<long long> result(v.size());
        for (int i = 0; i < result.size(); ++i)
            result[i] = llround(buf1[i].x);
        return result;
    }

    vector<long long> multiply(const vector<int> &a, const vector<int> &b) {
        if (a.empty() || b.empty()) return {};
        int n = 2;
        while (n < a.size() + b.size() - 1) n <<= 1;

        buf1.assign(n, {0, 0});

        for (int i = 0; i < a.size(); ++i)
            buf1[i].x = a[i];
        for (int i = 0; i < b.size(); ++i)
            buf1[i].y = b[i];

        fft_internal(buf1, 0, n, false);

        for (int i = 0; i <= (n >> 1); ++i) {
            // a --fft--> a1 + a2*i
            // b --fft--> b1 + b2*i
            // fact: FFT(a)[k] = FFT(a)[n - k].conj()
            // using this we can get formulas for FFT(a) and FFT(b) from FFT(a+bi)

            int j = (n - i) & (n - 1);

            auto v = (buf1[i] + buf1[j].conj()) * (buf1[i] - buf1[j].conj()) / 4;
            swap(v.x, v.y);

            buf1[i] = v.conj();
            buf1[j] = v;
        }

        fft_internal(buf1, 0, n, true);

        vector<long long> result(a.size() + b.size() - 1);
        for (int i = 0; i < result.size(); ++i)
            result[i] = llround(buf1[i].x);
        return result;
    }

    vector<int> multiply_mod(const vector<int> &a, const vector<int> &b, int mod) {
        if (a.empty() || b.empty()) return {};
        int n = 2;
        while (n < a.size() + b.size() - 1) n <<= 1;

        buf1.assign(n * 2, {0, 0});
        for (int i = 0; i < a.size(); ++i) {
            buf1[i].x = a[i] & ((1 << 15) - 1);
            buf1[i].y = a[i] >> 15;
        }
        buf2.assign(n * 2, {0, 0});
        for (int i = 0; i < b.size(); ++i) {
            buf2[i].x = b[i] & ((1 << 15) - 1);
            buf2[i].y = b[i] >> 15;
        }

        fft_internal(buf1, 0, n, false);
        fft_internal(buf2, 0, n, false);

        for (int i = 0; i <= (n >> 1); ++i) {
            int j = (n - i) & (n - 1);

            Complex as = (buf1[i] + buf1[j].conj()) / 2;
            Complex bs = (buf2[i] + buf2[j].conj()) / 2;
            Complex al = (buf1[i] - buf1[j].conj()) / 2;
            Complex bl = (buf2[i] - buf2[j].conj()) / 2;

            Complex asbs = as * bs;
            Complex albs = al * bs;
            Complex asbl = as * bl; swap(asbl.x, asbl.y);
            Complex albl = al * bl; swap(albl.x, albl.y);

            buf1[i] = asbs + albl.conj();
            buf1[j] = asbs.conj() - albl;

            buf2[i] = asbl.conj() + albs;
            buf2[j] = asbl - albs.conj();
        }

        fft_internal(buf1, 0, n, true);
        fft_internal(buf2, 0, n, true);

        vector<int> result(a.size() + b.size() - 1);
        for (int i = 0; i < result.size(); ++i) {
            long long asbs = llround(buf1[i].x);
            long long albl = llround(buf1[i].y);
            long long asbl = llround(buf2[i].x);
            long long albs = llround(buf2[i].y);
            result[i] = (((albl % mod) << 30) + (((asbl + albs) % mod) << 15) + asbs) % mod;
        }
        return result;
    }

} // fft

void solve() {
    int n;
    cin >> n;
    string s[4];
    vector<bool> good[4];
    string tar = "TTPC";
    for(int i=0;i<4;i++)cin >> s[i],good[i].resize(s[i].size());
    for(int i=0;i<4;i++){
        for(int j=0;j<s[i].size();j++) {
            if(s[i][j]==tar[i])good[i][j]=1;
        }
    }
    vector<int> num[2];
    for(int pa=0;pa<2;pa++){
        ll len = lcm(s[2*pa].size(),s[2*pa+1].size());
        num[pa].resize(len);
        for(int i = 0; i < len; ++i){
            num[pa][i]=(good[2*pa][i%good[2*pa].size()]&&good[2*pa+1][i%good[2*pa+1].size()]);
        }
    }
    auto rnum1 = num[1];
    reverse(all(rnum1));
    auto diffs = fft::multiply(num[0],rnum1);
    ll g = gcd(num[0].size(), num[1].size());
    ll prd = lcm(num[0].size(), num[1].size());
    ll eff = 0;
    for(int i=0;i<diffs.size();i++){
        if((i-(ll(num[1].size())-1))%g==0)eff += diffs[i];
    }
    if(eff==0){
        cout << "-1\n";
        return;
    }
    ll cur=(n-1)/eff*prd;
    n-=(n-1)/eff*eff;
    ll na[2]={cur+(ll)num[0].size(),cur+(ll)num[1].size()};
    while(true) {
        ll d = cur%num[0].size()-cur%num[1].size() + num[1].size()-1;
//        cerr << n << " " << d << " " << diffs[d] << endl;
        if(diffs[d]>=n) {
            while(true) {
                if(num[0][cur%num[0].size()]&&num[1][cur%num[1].size()]){
                    n--;
                    if(n==0){
                        cout << cur+1 << "\n";
                        return;
                    }
                }
                cur++;
            }
        }
        else {
            n-=diffs[d];
            if(na[0]<na[1]){
                cur=na[0];
                na[0]+=num[0].size();
            }
            else {
                cur=na[1];
                na[1]+=num[1].size();
            }
        }
    }
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}