// https://oj.uz/problem/view/APIO15_bridge
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
// K=1,2, N=1e5, 需要O(nlogn)
// 1. 家和办公室在同一边的是不参与计算的，和桥没有关系。
// 2. 最小值都在event点上面取得，而且是一个U型的阶梯函数，所以应该可以固定一个桥的位置，然后binary search另外一个。
// 3. 进一步可以发现K=1的时候，答案就是S[i], T[i]的median.
// 4. K=2的时候，简单做法是可以暴力搜索O(n^3)，这样可以得到31分。
// 5. 正解：把|s-x|+|t-x|画出来，就可以看到，是U型左右对称，所以有两个桥的时候，应该走的是离
// (s+t)/2近的桥。所以可以按(s+t)/2排序，分成两段后分别求median。这里可以用sliding median
// 的方法（两个multiset求siding median），O(nlogn).
// 收获：解题需要画图和抽象成公式，需要在纸上抠细节，就能找到正确解法。
int n, K;
ll ans;
vector<pair<int,int>> x;
// sliding median with 2 multisets
struct median {
multiset<int> l, r; // l is smaller part. size(l) >= size(r)
ll lsum, rsum;
median() {
lsum = 0; rsum = 0;
}
void balance() {
while (l.size() > r.size() + 1) {
int x = *prev(l.end());
r.insert(x);
l.erase(l.find(x));
rsum += x, lsum -= x;
}
while (r.size() > l.size()) {
int x = *r.begin();
l.insert(x);
r.erase(r.find(x));
lsum += x, rsum -= x;
}
}
void add(int x) {
if (l.empty()) {
l.insert(x);
lsum = x;
return;
}
if (x > get()) {
r.insert(x);
rsum += x;
} else {
l.insert(x);
lsum += x;
}
balance();
}
int get() {
return l.empty() ? -1 : *prev(l.end());
}
void del(int x) {
if (x > get())
r.erase(r.find(x)), rsum -= x;
else
l.erase(l.find(x)), lsum -= x;
balance();
}
};
int main() {
scanf("%d %d", &K, &n);
for (int i = 0; i < n; i++) {
char c1[10], c2[10];
int x1, x2;
scanf("%s %d %s %d", c1, &x1, c2, &x2);
if (c1[0] == c2[0]) ans += abs(x1-x2);
else x.push_back({min(x1,x2), max(x1,x2)});
}
vector<int> X;
for (auto p: x) {
X.push_back(p.first);
X.push_back(p.second);
}
sort(X.begin(), X.end());
if (K == 1 && x.size()) {
// just return the median of all numbers
int m = X[X.size() / 2];
for (auto p: x)
ans += abs(p.first-m) + abs(p.second-m) + 1;
} else if (K==2 && x.size()) {
// 正解
median l, r; // l is smaller
// sort x by (s+t)/2
sort(x.begin(), x.end(), [](pi a, pi b) {
return (a.first+a.second) < (b.first+b.second);
});
// initially everything in 'r'
ll sum = 0;
for (int p: X)
r.add(p);
int mr = r.get();
ll ans2 = r.rsum - r.lsum + x.size();
// move pairs one by one from r to l
for (pi p: x) {
l.add(p.first), l.add(p.second);
r.del(p.first), r.del(p.second);
ll sum = l.rsum - l.lsum + r.rsum - r.lsum + x.size();
ans2 = min(ans2, sum);
}
ans += ans2;
}
printf("%lld", ans);
return 0;
}
