#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(void){
ios::sync_with_stdio(0); cin.tie(0);
ll k,n,i,j;
cin>>k>>n;
vector<ll> s(n),t(n);
vector<char> p(n),q(n);
ll ans=0,val=1e18,cnt=0;
for(i=0 ; i<n ; i++){
cin>>p[i]>>s[i]>>q[i]>>t[i];
if(p[i]==q[i]){
cnt++;
ans+=abs(s[i]-t[i]);
continue;
}
}
if(cnt==n){
cout<<ans<<"\n";
return 0;
}
if(k==1){
vector<vector<ll>> pos;
map<ll,ll> mp,mp1;
for(i=0 ; i<n ; i++){
if(p[i]==q[i]) continue;
pos.push_back({s[i],i,0});
pos.push_back({t[i],i,1});
mp[s[i]]++;
mp[t[i]]++;
}
ll x=0,y,last=0;
for(auto v:mp){
y=v.second;
if(x!=0) mp1[v.first]=x;
if(x!=0) mp[v.first]=v.first-last;
x+=y;
last=v.first;
}
sort(pos.begin(),pos.end());
ll valtmp=0,brpos;
if(pos.size()) brpos=pos[0][0];
for(auto v:pos){
if(v[2]==0) valtmp+=abs(brpos-v[0])+abs(brpos-t[v[1]])+1;
}
val=min(val,valtmp);
for(auto v:mp1){
valtmp+=v.second*mp[v.first];
valtmp-=(pos.size()-v.second)*mp[v.first];
val=min(val,valtmp);
}
ans+=val;
cout<<ans<<"\n";
}
else{
ll sz=0;
map<ll,ll> mp1,mp2,mp,mp3,revmp;
set<pair<ll,ll>> st;
for(i=0 ; i<n ; i++){
if(p[i]==q[i]) continue;
mp1[min(s[i],t[i])]++;
mp1[min(s[i],t[i])]--;
mp1[max(t[i],s[i])]+=2;
mp3[-max(s[i],t[i])]++;
mp3[-max(s[i],t[i])]--;
mp3[-min(s[i],t[i])]+=2;
sz+=2;
}
cnt=0;
for(auto v:mp1){
revmp[v.first]=cnt;
mp[cnt++]=v.first;
}
vector<ll> pre,suff;
ll x=0,y=0;
for(auto v:mp1){
pre.push_back(x);
x+=v.second;
}
suff.resize(pre.size());
x=0,y=0;
for(auto v:mp3){
suff[revmp[-v.first]]=x+v.second;
x+=v.second;
}
sz=pre.size();
ll p1=-1,p2=1,val=1e18,valtmp1=0;
x=0;
mp[-1]=mp[0];
while(p1<sz-2){
p1++;
if(p1==0 and p2==1){
for(j=0 ; j<n ; j++){
if(p[j]==q[j]) continue;
valtmp1+=min(abs(mp[0]-t[j])+abs(mp[0]-s[j]),abs(mp[1]-t[j])+abs(mp[1]-s[j]))+1;
if(t[j]>s[j]) swap(t[j],s[j]);
if(abs(mp[0]-t[j])+abs(mp[0]-s[j])<=abs(mp[1]-t[j])+abs(mp[1]-s[j])) continue;
st.insert({(t[j]-mp[0])-(mp[1]-s[j]),j});
}
}
x+=mp[p1]-mp[p1-1];
val=min(val,valtmp1);
valtmp1+=pre[p1-1]*(mp[p1]-mp[p1-1]);
while(st.size()){
ll ac=(*st.begin()).first;
ll u=(*st.begin()).second;
if(ac-x<=0){
st.erase(st.begin());
valtmp1-=abs(mp[p2]-t[u])+abs(mp[p2]-s[u])+1;
valtmp1+=abs(mp[p1]-t[u])+abs(mp[p1]-s[u])+1;
}
else break;
}
val=min(val,valtmp1);
while(p2<sz-1){
p2++;
ll valtmp2=valtmp1;
x+=mp[p2]-mp[p2-1];
valtmp2-=suff[p2]*(mp[p2]-mp[p2-1]);
while(st.size()){
ll ac=(*st.begin()).first;
ll u=(*st.begin()).second;
if(ac-x<=0){
st.erase(st.begin());
valtmp2-=abs(mp[p2]-t[u])+abs(mp[p2]-s[u])+1;
valtmp2+=abs(mp[p1]-t[u])+abs(mp[p1]-s[u])+1;
}
else break;
}
if(valtmp1<valtmp2){
x-=mp[p2]-mp[p2-1];
p2--;
break;
}
valtmp1=valtmp2;
}
val=min(val,valtmp1);
}
ans+=val;
cout<<ans<<"\n";
}
return 0;
}
