#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
const ll inf = 1e18 ;
const int MAXN = 1e5+10 ;
using namespace std ;
int N , K ;
long long ans ;
vector< vector<int> > sweep ;
vector< vector<int> > sweepIni ;
vector<ll> p , pref, suf, qtdPref, qtdSuf ;
multiset<tuple<ll,ll,ll> > s[2] ;
multiset<ll> ss[2] ;
ll fat ;
ll toSum[2] , toSubtract[2] , qtdSum[2] , qtdSubtract[2] , val[2] ;
void add(int i, int j, int idx )
{
for(auto e : sweep[j] )
{
if(e <= i ) continue ;
toSubtract[idx] += p[j-1] ;
qtdSubtract[idx]++ ;
s[idx].insert( make_tuple( p[j-1] + p[e-1] - p[i-1] + fat , p[e-1] , p[j-1] ) ) ;
}
}
void print(int idx )
{
printf("Printing index %d\n", idx ) ;
for(auto e : s[idx] ) printf("%lld %lld %lld\n", get<0>(e), get<1>(e) , get<2>(e) ) ;
printf("toSum %lld, qtdSum %lld\ntoSubtract %lld, qtdSubtract %lld\n\n", toSum[idx], qtdSum[idx], toSubtract[idx], qtdSubtract[idx] ) ;
}
void compress(int i , int j,int idx )
{
while( !s[idx].empty() && p[j-1] >= get<0>(*s[idx].begin() )-fat )
{
auto t = *s[idx].begin() ;
s[idx].erase(s[idx].begin() ) ;
toSubtract[idx] -= get<2>(t) ;
qtdSubtract[idx]-- ;
if( get<1>(t) <= p[i-1] ) continue ;
toSum[idx] += get<1>(t) ;
qtdSum[idx]++ ;
ss[idx].insert( get<1>(t) ) ;
}
while( !ss[idx].empty() && p[i-1] >= *ss[idx].begin() )
{
toSum[idx] -= *ss[idx].begin() ;
qtdSum[idx]-- ;
ss[idx].erase(ss[idx].begin() ) ;
}
}
ll getAns(int i, int j , int idx) { return qtdPref[i] * p[i-1] - pref[i] + suf[j] - qtdSuf[j] * p[j-1] + toSum[idx] - qtdSum[idx]*p[i-1] + qtdSubtract[idx]*p[j-1] - toSubtract[idx] ; }
int main()
{
scanf("%d %d", &K , &N ) ;
vector<pair<int,int> > intervals ;
for(int i= 1; i <= N ; i++ )
{
char z1, z2 ;
int x, y ;
scanf(" %c %d %c %d", &z1, &x, &z2, &y ) ;
if( x > y ) swap(x,y) ;
ans += (ll)(y-x) ;
if( z1 == z2 ) continue ;
ans++ ;
intervals.push_back(make_pair(x,y) ) ;
p.push_back(x) ;
p.push_back(y) ;
}
sort(all(p) ) ;
p.erase(unique(all(p) ), p.end() ) ;
pref.resize( sz(p)+5 , 0 ) ; suf.resize(sz(p)+5, 0 ) ;
qtdPref.resize(sz(p) + 5 , 0 ) ; qtdSuf.resize(sz(p)+5, 0 ) ;
for(auto &e : intervals )
{
e.first = lower_bound(all(p), e.first ) - p.begin() + 1 ;
e.second = lower_bound(all(p), e.second ) - p.begin() + 1 ;
pref[e.second+1] += (ll)p[e.second-1] ;
qtdPref[e.second+1]++ ;
suf[e.first-1] += (ll)(p[e.first-1]) ;
qtdSuf[e.first-1]++ ;
}
for(int i= 1 ; i <= sz(p) ; i++ ) pref[i] += pref[i-1] , qtdPref[i] += qtdPref[i-1] ;
for(int i = sz(p) ; i >= 0 ; i-- ) suf[i] += suf[i+1] , qtdSuf[i] += qtdSuf[i+1] ;
long long mn = (sz(intervals) == 0 ) ? 0 : inf ;
for(int i = 1 ; i <= sz(p) ; i++ ) mn = min( mn, (qtdPref[i]-qtdSuf[i] )*p[i-1] -pref[i] + suf[i] ) ;
if( sz(p) == 2 && K == 2 ) mn = 0 ;
if( K == 1 || sz(p) <= 2 )
{
printf("%lld\n", ans + 2LL * mn ) ;
return 0 ;
}
// -------------- tricky part begins here --------------
sweep.resize( sz(p)+5 , vector<int>() ) ;
sweepIni.resize( sz(p)+5 , vector<int>() ) ;
for(auto e : intervals )
{
sweep[e.second].push_back( e.first ) ;
sweepIni[e.first].push_back( e.second ) ;
}
add(1,1,0) ; add(1,2,0) ;
add(1,1,1) ; add(1,2,1) ; add(1,3,1) ;
for(int opt = 2 , i = 1 ; i < sz(p) ; i++ )
{
compress(i,opt,0) ;
if( opt+1 <= sz(p) ) compress(i,opt+1, 1) ;
val[0] = getAns(i,opt,0) ;
val[1] = (opt+1 <= sz(p) ) ?getAns(i,opt+1,1) : inf ;
while( opt < i || (opt < sz(p) && val[1] <= val[0]) )
{
add(i,++opt,0) ; compress(i,opt,0) ;
if( opt+1 <= sz(p) )
{
add(i, opt+1, 1) ;
compress(i,opt+1, 1 ) ;
}
val[0] = getAns(i,opt,0) ;
val[1] = (opt+1 <= sz(p) ) ? getAns(i,opt+1,1) : inf ;
// cout << i << " " << opt << " " << val[0] << endl ;
}
if( val[0] < mn ) mn = val[0] ;
fat += p[i] - p[i-1] ;
}
printf("%lld\n", ans + 2LL*mn ) ;
}
