#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())
// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)
using namespace std;
typedef long long ll;
const int maxN = 2e5+7;
int k, n, sz;
ll fix;
vector<pair<int, int>> ed;
vector<int> df;
map<int, int> mp;
int demp[maxN];
pair<int, int> pr[maxN];
vector<int> st[maxN], en[maxN];
ll dis(pair<int, int> a, ll p){
return abs(a.fr-p)+abs(a.sc-p)+1;
}
int sumer(pair<int, int> a){
return a.fr+a.sc;
}
int sumer(int a, int b){
return a+b;
}
signed main(){IOS
cin >> k >> n;
for(int i = 0; i < n; i++){
char t1, t2;
int x1, x2;
cin >> t1 >> x1 >> t2 >> x2;
if(t1 == t2){
fix += abs(x2-x1);
}
else{
ed.push_back({min(x1, x2), max(x1, x2)});
df.push_back(x1);
df.push_back(x2);
}
}
n = ed.size();
uni(df);
sz = df.size();
if(sz == 1){
cout << 0 << '\n';
return 0;
}
for(int i = 0; i < sz; i++)mp[df[i]] = i, demp[i] = df[i];
for(int i = 0; i < n; i++){
ed[i].fr = mp[ed[i].fr];
ed[i].sc = mp[ed[i].sc];
pr[i] = {ed[i].fr, ed[i].sc};
st[ed[i].fr].push_back(i);
en[ed[i].sc].push_back(i);
}
if(k == 1){
int po = 0;
ll now = 0;
int l = en[po].size(), r = n-st[po].size();
for(int i = 0; i < n; i++){
ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]);
now += x;
}
ll ans = now;
while(po+1 < sz){
ll delt = demp[po+1]-demp[po];
now += (l*2-r*2)*delt;
ans = min(ans, now);
po++;
l += en[po].size();
r -= st[po].size();
}
cout << fix+ans << '\n';
return 0;
}
ll ans = 1e15;
for(int i = 1; i < sz; i++){
priority_queue<pair<int, int>> pq;
ll nw = 0;
for(int j = 0; j < ed.size(); j++){
if(ed[j].sc < i)pq.push({-sumer(ed[j]), j});
nw += dis({demp[ed[j].fr], demp[ed[j].sc]}, demp[i]);
}
for(int j = 0; j < i; j++){
while(pq.size() && -pq.top().fr < i+j){
nw -= dis({demp[pr[pq.top().sc].fr], demp[pr[pq.top().sc].sc]}, demp[i]);
nw += dis({demp[pr[pq.top().sc].fr], demp[pr[pq.top().sc].sc]}, demp[j]);
pq.pop();
}
ans = min(ans, nw);
}
}
cout << fix+ans << '\n';
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
===
24
===
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
===
22
===
2 10
A 1 B 1
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 6 B 10
A 6 B 10
===
18
===
*/
