//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

mt19937 rng(4242);

const int max_n = -1, inf = 1000111222;

template<int mod>
struct NTT {
    static constexpr int max_lev = __builtin_ctz(mod - 1);

    int prod[2][max_lev - 1];

    NTT() {
        int root = (mod == 998244353) ? 31 : find_root();
        int rroot = inv(root);
        vector<vector<int>> roots(2, vector<int>(max_lev - 1));
        roots[0][max_lev - 2] = root;
        roots[1][max_lev - 2] = rroot;
        for (int tp = 0; tp < 2; ++tp) {
            for (int i = max_lev - 3; i >= 0; --i) {
                roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
            }
        }
        for (int tp = 0; tp < 2; ++tp) {
            int cur = 1;
            for (int i = 0; i < max_lev - 1; ++i) {
                prod[tp][i] = mul(cur, roots[tp][i]);
                cur = mul(cur, roots[tp ^ 1][i]);
            }
        }
    }

    template<bool inverse>
    void fft(int *a, int lg) const {
        const int n = 1 << lg;
        int pos = max_lev - 1;
        for (int it = 0; it < lg; ++it) {
            const int h = inverse ? lg - 1 - it : it;
            const int shift = (1 << (lg - h - 1));
            int coef = 1;
            for (int start = 0; start < (1 << h); ++start) {
                for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
                    if (!inverse) {
                        const int y = mul(a[i + shift], coef);
                        a[i + shift] = a[i];
                        inc(a[i], y);
                        dec(a[i + shift], y);
                    } else {
                        const int y = mul(a[i] + mod - a[i + shift], coef);
                        inc(a[i], a[i + shift]);
                        a[i + shift] = y;
                    }
                }
                coef = mul(coef, prod[inverse][__builtin_ctz(~start)]);
            }
        }
        if (inverse) {
            const int rn = inv(n);
            for (int i = 0; i < n; ++i) {
                a[i] = mul(a[i], rn);
            }
        }
    }

    vector<int> product(vector<int> a, vector<int> b) const {
        if (a.empty() || b.empty()) {
            return {};
        }
        const int sz = a.size() + b.size() - 1;
        const int lg = ((sz == 1) ? 0 : (32 - __builtin_clz(sz - 1))), n = 1 << lg;
        a.resize(n);
        b.resize(n);
        fft<false>(a.data(), lg);
        fft<false>(b.data(), lg);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], b[i]);
        }
        fft<true>(a.data(), lg);
        a.resize(sz);
        return a;
    }

    vector<int> square(vector<int> a) const {
        if (a.empty()) {
            return {};
        }
        const int sz = a.size() + a.size() - 1;
        const int lg = ((sz == 1) ? 0 : (32 - __builtin_clz(sz - 1))), n = 1 << lg;
        a.resize(n);
        fft<false>(a.data(), lg);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], a[i]);
        }
        fft<true>(a.data(), lg);
        a.resize(sz);
        return a;
    }

    static int find_root() {
        for (int root = 2; ; ++root) {
            if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
                return root;
            }
        }
    }

    static inline void inc(int &x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }

    static inline void dec(int &x, int y) {
        x -= y;
        if (x < 0) {
            x += mod;
        }
    }

    static inline int mul(int x, int y) {
        return (1LL * x * y) % mod;
    }

    static int power(int x, int y) {
        if (y == 0) {
            return 1;
        }
        if (y % 2 == 0) {
            return power(mul(x, x), y / 2);
        }
        return mul(x, power(x, y - 1));
    }

    static int inv(int x) {
        return power(x, mod - 2);
    }
};

NTT<998244353> ntt;

bool DBG = false;

void solve() {
    ll n;
    cin >> n;
    vector<string> s(4);
    for(int i = 0; i < 4; i++) {
        if(DBG) {
            for(int j = 0; j < 1000; j++) s[i] += "TTPC"[rng() % 4];
        } else cin >> s[i];
    }
    string need = "TTPC";
    int sz[4] = {len(s[0]), len(s[1]), len(s[2]), len(s[3])};
    if(sz[0] * sz[1] < sz[2] * sz[3]) {
        swap(s[0], s[2]);
        swap(s[1], s[3]);
        swap(need[0], need[2]);
        swap(need[1], need[3]);
        swap(sz[0], sz[2]);
        swap(sz[1], sz[3]);
    }
    int N = sz[0] * sz[1], M = sz[2] * sz[3];
    vector<int> a(N * 2), b(M);
    for(int i = 0; i < N; i++) a[i] = a[i + N] = (s[0][i % len(s[0])] == need[0] && s[1][i % len(s[1])] == need[1]);
    for(int i = 0; i < M; i++) b[i] = (s[2][i % len(s[2])] == need[2] && s[3][i % len(s[3])] == need[3]);
    vector<int> pos;
    int cr = 0;
    while(true) {
        pos.pb(cr);
        cr = (cr + M) % N;
        if(!cr) break;
    }
//    for(auto& x : a) cout << x << ' '; cout << '\n';
//    for(auto& x : b) cout << x << ' '; cout << '\n';
    reverse(all(b));
    auto prod = ntt.product(a, b);
    reverse(all(b));
    vector<ll> kek;
    for(int i = 0; i < N; i++) kek.pb(prod[i + len(b) - 1]);
    ll tot = 0;
    for(auto& x : pos) tot += kek[x];
    ll tot_sz = len(pos) * 1ll * M;
    if(!tot) {
        cout << "-1\n";
        return;
    }
    ll full = (n - 1) / tot;
    ll rem = n - full * tot;
    ll ans = full * tot_sz;
    for(auto& x : pos) {
        if(rem - kek[x] <= 0) {
            int pos_a = x, pos_b = 0;
            for(int i = 0; i < M; i++) {
                ans++;
                if(a[pos_a] && b[pos_b]) {
                    rem--;
                    if(!rem) break;
                }
                pos_a = (pos_a + 1) % N;
                pos_b = (pos_b + 1) % M;
            }
            break;
        } else {
            rem -= kek[x];
            ans += M;
        }
    }
    cout << ans << '\n';
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

//    cin >> t;

    while (t--) solve();

}

/*
KIVI
*/