#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
const int MAXN = 500100;
const ll INF = (ll)1e17;
struct median {
ll sum1 = 0, sum2 = 0;
priority_queue<ll> q1;
priority_queue<ll, vl, greater<ll>> q2;
void clear () {
sum1 = sum2 = 0;
while (!q1.empty()) {q1.pop();}
while (!q2.empty()) {q2.pop();}
}
void ins (ll s, ll t) {
if (q1.empty()) {
q1.push(s); sum1 += s;
q2.push(t); sum2 += t;
return;
}
ll a = q1.top(); q1.pop(); sum1 -= a;
ll b = q2.top(); q2.pop(); sum2 -= b;
if (b < s) swap(b, s);
if (t < a) swap(a, t);
q1.push(a); sum1 += a;
q1.push(s); sum1 += s;
q2.push(b); sum2 += b;
q2.push(t); sum2 += t;
}
ll get () {
return sum2 - sum1;
}
};
int k, nn, n;
ll s[MAXN], t[MAXN];
vl pts;
set<ll> tmp;
map<ll, int> toId;
ll ans;
vector<pair<ll, int>> sortedS, sortedT, sortedST;
ll closed[MAXN], notOpened[MAXN];
void preCalc () {
/// compression of points
FOR(i, 1, n) {
tmp.insert(s[i]);
tmp.insert(t[i]);
}
ll id = 0;
for (ll x : tmp) {
pts.pb(x);
toId[x] = id;
id++;
}
/// sortedS and sortedT
FOR(i, 1, n) {
sortedS.pb({s[i], i});
sortedT.pb({t[i], i});
sortedST.pb({s[i] + t[i], i});
}
sort(sortedS.begin(), sortedS.end());
sort(sortedT.begin(), sortedT.end());
sort(sortedST.begin(), sortedST.end());
/// closed and notOpen calc
notOpened[0] = n;
FOR(i, 1, n) {
notOpened[toId[s[i]]]--;
closed[toId[t[i]]]++;
}
FOR(i, 1, (int)pts.size()-1) {
notOpened[i] += notOpened[i-1];
closed[i] += closed[i-1];
}
}
ll solve1 () {
//ll curMin = INF;
ll cur = 0;
int ch = 0;
FOR(i, 0, (int)pts.size()-1) {
if (closed[i] >= notOpened[i]) {
ch = pts[i];
break;
}
}
FOR(i, 1, n) {
cur += abs(s[i] - ch) + abs(t[i] - ch);
}
//ans += cur;
//cout << ans << "\n";
return ans+cur;
}
ll pref[MAXN], suf[MAXN];
ll solve2 () {
ll cur = 0;
ll minCur = INF;
median m;
m.clear();
FOR(i, 0, n-1) {
int id = sortedST[i].s;
m.ins(s[id], t[id]);
pref[i] = m.get();
// cout << " i = " << i << " id = " << id << " pref i = " << pref[i] << endl;
}
m.clear();
for (int i = n-1; i >= 0; i--) {
int id = sortedST[i].s;
m.ins(s[id], t[id]);
suf[i] = m.get();
//cout << " i = " << i << " id = " << id << " suf i = " << suf[i] << endl;
}
minCur = suf[0];
FOR(i, 0, n-2) {
minCur = min(minCur, pref[i] + suf[i+1]);
}
return ans+minCur;
}
int main()
{
FAST_IO;
cin >> k >> nn;
FOR(i, 1, nn) {
char pp, qq;
ll ss, tt;
cin >> pp >> ss >> qq >> tt;
if (pp == qq) {
ans += abs(ss-tt);
} else {
n++;
ans++;
//ans += abs(ss-tt);
s[n] = min(ss,tt);
t[n] = max(ss,tt);
}
}
//cout << " ans = " << ans << endl;
preCalc();
if (k == 1 || (int)pts.size() == 1) {
cout << solve1() << "\n";
return 0;
} else {
ll asa = min(solve1(), solve2());
cout << asa << "\n";
return 0;
}
return 0;
}
/*
in:
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
ans: 24
in:
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
ans: 22
in:
2 3
A 0 B 5
A 0 B 4
A 1 B 5
*/
