//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> gen(string s,string t,string pat)
{
	vector<int> res(sz(s)*sz(t));
	for(int i=0;i<sz(res);i++)
		if(s[i%sz(s)]==pat[0]&&t[i%sz(t)]==pat[1])
			res[i]=1;
	return res;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	n--;
	string A,B,C,D;
	cin>>A>>B>>C>>D;
	vector<int> v1=gen(A,B,"TT"),v2=gen(C,D,"PC");
	int a=sz(v1),b=sz(v2),g=__gcd(a,b);
	vector<vector<int>> vs(g),vt(g);
	for(int i=0;i<a;i++)
		vs[i%g].pb(v1[i]);
	for(int i=0;i<b;i++)
		vt[i%g].pb(v2[i]);
	ll tot=0;
	for(int i=0;i<g;i++)
		tot+=accumulate(ALL(vs[i]),0ll)*accumulate(ALL(vt[i]),0ll);
	if(!tot) die("-1");
	ll ans=1ll*a*b/g*(n/tot);
	n%=tot;
	ll l=0,r=a*b/g;
	while(l<r)
	{
		ll mid=(l+r)/2;
		ll cnt=0;
		for(int i=0;i<g;i++)
		{
			vector<ll> psum(b/g);
			vector<int> ord(b/g);
			for(int j=0;j<sz(vt[i]);j++)
				psum[j]=vt[i][j];
			int c=0;
			ll lst=0;
			for(int j=0;j<sz(vt[i]);j++)
			{
				int x=1ll*sz(vs[i])*j%sz(vt[i]);
				ord[x]=c++;
				psum[x]+=lst;
				lst=psum[x];
			}
			for(int j=0;j<sz(vs[i]);j++)
				if(vs[i][j])
				{
					int pos=j*g+i;
					if(mid<pos) continue;
					ll times2=(mid-pos)/a+1;
					int st=j%sz(vt[i]);
					int nd=(j+(times2-1)*sz(vs[i]))%sz(vt[i]);
					if(ord[nd]>=ord[st])
						cnt+=psum[nd]-psum[st]+vt[i][st];
					else
						cnt+=lst-psum[st]+psum[nd]+vt[i][st];
				}
		}
		if(cnt<=n)
			l=mid+1;
		else
			r=mid;
	}
	cout<<ans+l+1<<endl;
	return 0;
}