#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll cost_one_bridge(const vector<pair<ll,ll>>& segs) {
vector<ll> pts;
for (auto &p : segs) {
pts.push_back(p.first);
pts.push_back(p.second);
}
sort(pts.begin(), pts.end());
ll x = pts[pts.size()/2];
ll cost = 0;
for (auto &p : segs) {
cost += abs(p.first - x) + abs(p.second - x) + 1;
}
return cost;
}
ll cost_group(const vector<pair<ll,ll>>& segs) {
if (segs.empty()) return 0;
vector<ll> pts;
for (auto &p : segs) {
pts.push_back(p.first);
pts.push_back(p.second);
}
sort(pts.begin(), pts.end());
ll x = pts[pts.size()/2];
ll cost = 0;
for (auto &p : segs) {
cost += abs(p.first - x) + abs(p.second - x) + 1;
}
return cost;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K, N;
cin >> K >> N;
ll answer = 0;
vector<pair<ll,ll>> cross;
for (int i = 0; i < N; i++) {
char P, Q;
ll S, T;
cin >> P >> S >> Q >> T;
if (P == Q) {
answer += llabs(S - T);
} else {
ll L = min(S, T);
ll R = max(S, T);
cross.push_back({L, R});
}
}
if (cross.empty()) {
cout << answer << "\n";
return 0;
}
if (K == 1) {
answer += cost_one_bridge(cross);
cout << answer << "\n";
return 0;
}
sort(cross.begin(), cross.end());
int M = cross.size();
vector<ll> pref(M+1), suff(M+2);
vector<pair<ll,ll>> tmp;
for (int i = 0; i < M; i++) {
tmp.push_back(cross[i]);
pref[i+1] = cost_group(tmp);
}
tmp.clear();
for (int i = M-1; i >= 0; i--) {
tmp.push_back(cross[i]);
suff[i+1] = cost_group(tmp);
}
ll best = LLONG_MAX;
for (int i = 0; i <= M; i++) {
best = min(best, pref[i] + suff[i+1]);
}
answer += best;
cout << answer << "\n";
}
