#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include <debug.h>
// #else
// #define debug(...)
// #endif
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;
int solve(vector <pair<int, int>> &v) {
if (v.empty()) return 0;
int n = v.size();
map <int, int> g;
int ls = INF;
for (int i = 0; i < n; i++) {
int l = v[i].ff, r = v[i].ss;
g[l] += 2;
g[r] += 2;
ls = min(ls, l-1);
}
int s = -2 * n;
int ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(ls - v[i].ff) + abs(ls - v[i].ss);
}
int mn = ans;
for (auto &[x, y] : g) {
ans += (x - ls) * s;
s += y;
mn = min(mn, ans);
ls = x;
}
return mn + n;
}
void _() {
int k, n;
cin >> k >> n;
int res = 0;
vector <pair<int, int>> v;
for (int i = 0; i < n; i++) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if (a == b) {
res += abs(x - y);
continue;
}
if (x > y) swap(x, y);
v.pb({x, y});
}
n = v.size();
if (n == 0) {
cout << res;
return;
}
vector <array <int, 3>> v1;
for (auto &i : v) v1.pb({i.ff + i.ss, i.ff, i.ss});
sort(all(v1));
for (int i = 0; i < n; i++) v[i] = {v1[i][1], v1[i][2]};
if (k == 1) {
cout << res + solve(v);
return;
}
vector <int> ans;
int sum = 0;
int m = 0;
int l = 0, r = 0;
multiset <int> ms;
auto it = ms.end();
auto add = [&](int a) {
if (ms.empty()) {
m = a;
ms.insert(a);
it = ms.begin();
return;
}
sum += abs(m - a);
ms.insert(a);
if (m <= a) {
r++;
}
else l++;
while (l + 1 < r) {
it++;
sum += (*it - m) * (l + 1 - r);
m = *it;
l++;
r--;
}
while (l + 1 > r) {
it--;
sum += m - *it;
m = *it;
l--;
r++;
}
};
for (int i = 0; i < n; i++) {
int a = v[i].ff, b = v[i].ss;
add(a);
add(b);
ans.pb(sum);
}
ms.clear();
l = r = m = sum = 0;
vector <int> ans1;
for (int i = n - 1; i >= 0; i--) {
int a = v[i].ff, b = v[i].ss;
add(a);
add(b);
ans1.pb(sum);
}
reverse(all(ans1));
int mn = min(ans.back(), ans1[0]);
for (int i = 1; i < n; i++) {
mn = min(mn, ans[i-1] + ans1[i]);
}
cout << res + n + mn;
}
signed main() {
GOOD_LUCK
int tests=1;
// cin >> tests;
for (int i=1; i <= tests; i++) {
_();
cout << endl;
}
return 0;
}
