#include<cstdio>
#include<algorithm>
int p[111111];
int s[111111];
int q[111111];
int t[111111];
char pp[11],qq[11];
std::pair<int,int> d[444444];
int dn;
int main()
{
//freopen("input","r",stdin);
long long res=0;
int i,j,n,m;
int fir,sec;
long long min,now,ang;
scanf("%d%d",&m,&n);
if(m==1)
{
j=0;
for(i=0;i<n;i++)
{
scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
p[i]=pp[0]-'A';
q[i]=qq[0]-'A';
if(p[i]!=q[i])
{
j++;
d[dn++]=std::make_pair(std::min(s[i],t[i]),-1);
d[dn++]=std::make_pair(std::max(s[i],t[i]),-1);
}
}
std::sort(d,d+dn);
for(i=0;i<dn;i++)
{
j+=d[i].second;
if(j<=0)break;
}
for(j=0;j<n;j++)
{
if(p[j]!=q[j])res+=std::abs(s[j]-d[i].first)+std::abs(t[j]-d[i].first)+1;
else res+=std::abs(s[j]-t[j]);
}
printf("%lld\n",res);
return 0;
}
for(i=0;i<n;i++)
{
scanf("%s%d%s%d",pp,&s[i],qq,&t[i]);
p[i]=pp[0]-'A';
q[i]=qq[0]-'A';
}
if(n<=1000)
{
res=9e18;
for(i=0;i<n;i++)
{
fir=s[i];
dn=0;
for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
{
d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
}
std::sort(d,d+dn);
min=now=ang=0;
sec=0;
for(j=0;j<dn;j++)
{
if(j)now+=ang*(d[j].first-d[j-1].first);
ang+=d[j].second;
if(now>min)
{
min=now;
sec=d[j].first;
}
}
now=0;
for(j=0;j<n;j++)
{
if(p[j]!=q[j])now+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
else now+=std::abs(s[j]-t[j]);
}
res=std::min(res,now);
fir=t[i];
dn=0;
for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
{
d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
}
std::sort(d,d+dn);
min=now=ang=0;
sec=0;
for(j=0;j<dn;j++)
{
if(j)now+=ang*(d[j].first-d[j-1].first);
ang+=d[j].second;
if(now>min)
{
min=now;
sec=d[j].first;
}
}
now=0;
for(j=0;j<n;j++)
{
if(p[j]!=q[j])now+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
else now+=std::abs(s[j]-t[j]);
}
res=std::min(res,now);
}
printf("%lld\n",res);
return 0;
}
sec=s[0];
for(i=1;i<=15;i++)
{
fir=sec;
dn=0;
for(j=0;j<n;j++)if(p[j]!=q[j]&&(std::max(s[j],t[j])<fir||std::min(s[j],t[j])>fir))
{
d[dn++]=std::make_pair(std::min(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::max(fir,s[j]+t[j]-fir),1);
d[dn++]=std::make_pair(std::min(s[j],t[j]),-1);
d[dn++]=std::make_pair(std::max(s[j],t[j]),-1);
}
std::sort(d,d+dn);
min=now=ang=0;
sec=s[i%n];
for(j=0;j<dn;j++)
{
if(j)now+=ang*(d[j].first-d[j-1].first);
ang+=d[j].second;
if(now>min)
{
min=now;
sec=d[j].first;
}
}
}
for(j=0;j<n;j++)
{
if(p[j]!=q[j])res+=std::min(std::abs(s[j]-fir)+std::abs(t[j]-fir),std::abs(s[j]-sec)+std::abs(t[j]-sec))+1;
else res+=std::abs(s[j]-t[j]);
}
printf("%lld\n",res);
}
