/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e5+200;
const ll mod=1e9+7 ;
const ll base=3e18;
/// you will be the best but now you just are trash
/// goal 1/7
vector<ll> vt;
struct tk
{
pll st[4*maxn];
tk()
{
for (int i=0; i<4*maxn; i++)
{
st[i]=make_pair(0,0);
}
}
pll mer(pll a,pll b)
{
return make_pair(a.ff+b.ff,a.ss+b.ss);
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left)
return ;
if (left==right)
{
st[id].ff+=diff;
st[id].ss+=diff*(vt[left-1]);
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid,x,diff);
update(id*2+1,mid+1,right,x,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
pll get(ll id,ll left,ll right,ll x,ll y)
{
if (x>right||y<left)
return make_pair(0,0);
if (x<=left&&y>=right)
{
return st[id];
}
ll mid=(left+right)/2;
return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
ll walk(ll id,ll left,ll right,ll val)
{
if (left==right)
return left;
ll mid=(left+right)/2;
// cout <<id<<" "<<left<<" "<<right<<" "<<val<<" "<<st[id*2].ss<<" chk"<<endl;
if (st[id*2].ff>=val)
return walk(id*2,left,mid,val);
else
return walk(id*2+1,mid+1,right,val-st[id*2].ff);
}
ll getall(ll n)
{
pll h=st[1];
ll sl=h.ff;
if (sl==0)
return 0;
ll nw=sl/2;
ll pos=walk(1,1,n,nw);
// cout <<pos<<" "<<vt[pos-1]<<" "<<sl<<" "<<nw<<endl;
auto p=get(1,1,n,1,pos);
auto p1=get(1,1,n,pos,n);
return p.ff*vt[pos-1]-p.ss-p1.ff*vt[pos-1]+p1.ss;
}
};
bool lf(pll a,pll b)
{
return (a.ff+a.ss<b.ff+b.ss);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll ans=0;
ll k, n;
cin>> k>> n;
vector<pll> vt1;
ll res=base;
for (int i=1; i<=n; i++)
{
char p,p1;
ll l, r;
cin>> p>> l>> p1>> r;
if (l>r)
swap(l,r);
if (p==p1)
{
ans+=(r-l);
}
else
{
ans++;
vt.pb(l);
vt.pb(r);
vt1.pb(make_pair(l,r));
}
}
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
sort(vt1.begin(),vt1.end(),lf);
tk man;
tk man1;
ll len=vt.size();
for (auto p:vt1)
{
ll l=lower_bound(vt.begin(),vt.end(),p.ff)-vt.begin()+1;
ll r=lower_bound(vt.begin(),vt.end(),p.ss)-vt.begin()+1;
// cout <<l<<" "<<r<<" "<<len<<endl;
man1.update(1,1,len,l,1);
man1.update(1,1,len,r,1);
}
res=min(res,man1.getall(len)+ans);
if (k==1)
{
cout<<res;
return 0;
}
for (auto p:vt1)
{
ll l=lower_bound(vt.begin(),vt.end(),p.ff)-vt.begin()+1;
ll r=lower_bound(vt.begin(),vt.end(),p.ss)-vt.begin()+1;
man1.update(1,1,len,l,-1);
man1.update(1,1,len,r,-1);
man.update(1,1,len,l,1);
man.update(1,1,len,r,1);
res=min(res,man1.getall(len)+man.getall(len)+ans);
}
cout <<res<<endl;
}
/*2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7*/
