#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#define INF 1000000000000000000LL
typedef struct node node;
struct node
{
int s, e;
};
std::set<long long> Event;
std::vector<long long> cEvent;
std::vector<node> incE, decS;
long long abs(long long a)
{
return (a < 0)?-a:a;
}
long long min(long long a, long long b)
{
return (a < b)?a:b;
}
long long max(long long a, long long b)
{
return (a > b)?a:b;
}
int sortIncE(node a, node b)
{
return (a.e < b.e || (a.e == b.e && a.s < b.s));
}
int sortDecS(node a, node b)
{
return (a.s > b.s || (a.s == b.s && a.e > b.e));
}
typedef struct se se;
struct se
{
long long sum;
int i;
};
bool operator<(se a, se b)
{
return (a.sum < b.sum || (a.sum == b.sum && a.i < b.i));
}
std::map<se, int> SE;
std::map<se, int>::iterator p, q;
int main()
{
int K, N;
scanf("%d %d", &K, &N);
int i, j, k;
int i2, j2, k2;
long long Obligatory = 0;
long long Sum1a = 0, Sum1b = 0;
long long Sum2a = 0, Sum2b = 0, Sum2c = 0;
char P, Q;
int S, T;
for (i = 0; i < N; i++)
{
scanf(" %c %d %c %d", &P, &S, &Q, &T);
if (P == Q)
{
Obligatory += abs(T - S);
}
else
{
Obligatory += 1 + abs(T - S);
incE.push_back({min(S, T), max(S, T)});
decS.push_back({min(S, T), max(S, T)});
Event.insert(S);
Event.insert(T);
}
}
// printf("Obligatory %lld\n", Obligatory);
std::set<long long>::iterator it;
for (it = Event.begin(); it != Event.end(); it++)
{
cEvent.push_back(*it);
// printf("cEvent %lld\n", *it);
}
N = incE.size();
for (i = 0; i < N; i++)
{
S = std::lower_bound(cEvent.begin(), cEvent.end(), incE[i].s) - cEvent.begin();
T = std::lower_bound(cEvent.begin(), cEvent.end(), incE[i].e) - cEvent.begin();
incE[i] = {S, T};
S = std::lower_bound(cEvent.begin(), cEvent.end(), decS[i].s) - cEvent.begin();
T = std::lower_bound(cEvent.begin(), cEvent.end(), decS[i].e) - cEvent.begin();
decS[i] = {S, T};
// printf("S%d T%d\n", S, T);
Sum1b += cEvent[S];
}
std::sort(incE.begin(), incE.end(), sortIncE);
std::sort(decS.begin(), decS.end(), sortDecS);
if (K == 2)
{
long long Ans = INF;
if (cEvent.size() == 0)
Ans = Obligatory;
j = 0;
k = N - 1;
for (i = 0; i < cEvent.size(); i++)
{
while (j < N && incE[j].e < i)
{
Sum1a += cEvent[incE[j].e];
SE.insert({{cEvent[incE[j].s] + cEvent[incE[j].e], j}, 0});
j++;
}
while (k >= 0 && decS[k].s == i)
{
Sum1b -= cEvent[decS[k].s];
k--;
}
j2 = 0;
k2 = j - 1;
p = SE.begin();
Sum2a = 0;
Sum2b = 0;
Sum2c = 0;
for (i2 = 0; i2 < i; i2++)
{
while (p != SE.end() && p->first.sum < cEvent[i] + cEvent[i2])
{
if (p->first.i <= k2)
{
p->second = 1;
Sum2c += 2LL*(cEvent[i] + cEvent[i2] - p->first.sum);
}
p++;
}
while (k2 >= 0 && decS[k2].s == i2)
{
q = SE.find({cEvent[decS[k2].s] + cEvent[decS[k2].e], k2});
if (q->second == 1)
{
Sum2c -= 2LL*(cEvent[i] + cEvent[i2] - q->first.sum);
q->second = 0;
}
Sum2b += 2LL*(cEvent[i] - cEvent[decS[k2].e]);
k2--;
}
while (j2 < j && incE[j2].e < i2)
{
Sum2b -= 2LL*(cEvent[i] - cEvent[incE[j2].e]);
Sum2a += 2LL*(cEvent[i] - cEvent[i2]);
j2++;
}
assert(Sum2a >= 0 && Sum2b >= 0 && Sum2c >= 0);
// printf("i2 %d j2 %d k2 %d Sum1a %lld Sum1b %lld Sum2a %lld Sum2b %lld Sum2c %lld = %lld\n", i2, j2, k2, Sum1a, Sum1b, Sum2a, Sum2b, Sum2c, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)) - Sum2a - Sum2b - Sum2c);
Ans = min(Ans, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)) - Sum2a - Sum2b - Sum2c);
}
// printf("i %d j %d k %d Sum1a %lld Sum1b %lld = %lld\n", i, j, k, Sum1a, Sum1b, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
Ans = min(Ans, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
}
printf("%lld", Ans);
}
else
{
long long Ans = INF;
if (cEvent.size() == 0)
Ans = Obligatory;
j = 0;
k = N - 1;
for (i = 0; i < cEvent.size(); i++)
{
while (j < N && incE[j].e < i)
{
Sum1a += cEvent[incE[j].e];
j++;
}
while (k >= 0 && decS[k].s == i)
{
Sum1b -= cEvent[decS[k].s];
k--;
}
// printf("j %d k %d Sum1a %lld Sum1b %lld = %lld\n", j, k, Sum1a, Sum1b, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
Ans = min(Ans, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
}
printf("%lld", Ans);
}
}
