#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const int N=2e6+3;
ll lcm(ll x,ll y){
    return x*y/__gcd(x,y);
}

ll exgcd(ll a,ll b,ll& x,ll& y){
	if(!b)return x=1,y=0,a;
	ll d=exgcd(b,a%b,y,x);
	y-=x*(a/b);
    return d;
}

pll excrt(ll m1,ll m2,ll x1,ll x2,ll x,ll y,ll d){
    ll m,c=(x2-x1%m2+m2)%m2;
    ll t=m2/d;
    if(c%d)return {-1,-1};
    x=(__int128)x*c/d%t;
    x=m1*x+x1,m=m1*t,x=(x%m+m)%m;
    return {x,m};
}

vector<ll> mrg(vector<ll> a,vector<ll> b,ll m1,ll m2){
    ll x,y;
    ll d=exgcd(m1,m2,x,y);
    vector<ll> res;
    for(ll x1:a)for(ll x2:b){
        pll t=excrt(m1,m2,x1,x2,x,y,d);
        if(t==pll(-1,-1))continue;
        res.push_back(t.first);
    }
    sort(res.begin(),res.end());
    return res;
}

namespace NTT{
const int L=1<<21,mod=998244353;
ll qpow(ll x,int y){
    ll r=1;
    for(;y;y>>=1){
        if(y&1)r=r*x%mod;
        x=x*x%mod;
    }
    return r;
}
ll inv(ll x){
    return qpow(x,mod-2);
}

int re[L];
ll w[2][L];
int init(int n){
    int len=1,bit=0;
    while(len<n)len<<=1,++bit;
    for(int i=1;i<len;++i)re[i]=(re[i>>1]>>1)|((i&1)<<(bit-1));
    w[0][0]=w[1][0]=1;
    w[0][1]=qpow(3,(mod-1)/len),w[1][1]=inv(w[0][1]);
    for(int o=0;o<2;++o)
        for(int i=2;i<len;++i)
            w[o][i]=w[o][i-1]*w[o][1]%mod;
    return len;
}
void NTT(ll* a,int n,int o=0){
    for(int i=1;i<n;++i)if(i<re[i])swap(a[i],a[re[i]]);
    ll R;
    for(int k=1;k<n;k<<=1)
        for(int i=0,t=k<<1,st=n/t;i<n;i+=t)
            for(int j=0,nw=0;j<k;++j,nw+=st){
                R=a[i+j+k]*w[o][nw]%mod;
                a[i+j+k]=(a[i+j]-R+mod)%mod;
                a[i+j]=(a[i+j]+R)%mod;
            }
    if(o){
        R=inv(n);
        for(int i=0;i<n;++i)a[i]=a[i]*R%mod;
    }
}

ll t0[L],t1[L];
void multi(ll* a,ll* b,ll* c,int n,int m){
    int len=init(n+m+1);
    memset(t0,0,sizeof(ll)*len);
    memcpy(t0,a,sizeof(ll)*(n+1));
    memset(t1,0,sizeof(ll)*len);
    memcpy(t1,b,sizeof(ll)*(m+1));
    NTT(t0,len),NTT(t1,len);
    for(int i=0;i<len;++i)t0[i]=t0[i]*t1[i]%mod;
    NTT(t0,len,1);
    memcpy(c,t0,sizeof(ll)*(n+m+1));
}
}

int n,l[4];
string s[4];
vector<ll> a[4];
vector<ll> b[2];
vector<pll> k;
ll f[N],g[N],h[N],cnt[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n,--n;
    for(int i=0;i<4;++i)cin>>s[i],l[i]=s[i].length();
    for(int i=0;s[0][i];++i)if(s[0][i]=='T')a[0].push_back(i);
    for(int i=0;s[1][i];++i)if(s[1][i]=='T')a[1].push_back(i);
    for(int i=0;s[2][i];++i)if(s[2][i]=='P')a[2].push_back(i);
    for(int i=0;s[3][i];++i)if(s[3][i]=='C')a[3].push_back(i);
    b[0]=mrg(a[0],a[1],l[0],l[1]);
    b[1]=mrg(a[2],a[3],l[2],l[3]);
    if(!b[0].size()||!b[1].size()){
        cout<<"-1\n";
        return 0;
    }
    ll L[2]={lcm(l[0],l[1]),lcm(l[2],l[3])};
    ll x,y;
    ll d=exgcd(L[0],L[1],x,y);
    for(int i=0;i<L[1];i+=d){
        ll c=i/d;
        k.push_back({(c*x%(L[1]/d)+L[1]/d)%(L[1]/d),i});
    }
    sort(k.begin(),k.end());
    for(ll x:b[0])f[L[0]-x-1]=1;
    for(ll x:b[1])g[x]=1;
    NTT::multi(f,g,h,L[0]-1,L[1]-1);
    ll sum=0;
    for(int i=-(L[0]-1);i<L[1];++i)if(!(i%d)){
        sum+=h[L[0]-1+i];
        cnt[(i%L[1]+L[1])%L[1]]+=h[L[0]-1+i];
    }
    if(!sum){
        cout<<"-1\n";
        return 0;
    }
    ll T=lcm(L[0],L[1]);
    ll ans=T*(n/sum);
    n%=sum;
    for(auto&[k1,i]:k){
        if(n>cnt[i])n-=cnt[i];
        else{
            for(ll x:b[0]){
                if(g[(x+i)%L[1]])--n;
                if(n<0){
                    cout<<ans+x+k1*L[0]+1<<'\n';
                    return 0;
                }
            }
        }
    }
}