/**
* author: marcus06
* created: 28-04-2026 19:28:44
**/
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
//sliding median
lli L_sum = 0, R_sum = 0;
multiset <int> L, R;
void balance() {
while (R.size() + 1 < L.size()) {
int value = *L.rbegin();
L_sum -= value;
R_sum += value;
R.insert(value);
L.erase(L.find(value));
}
while (!R.empty() && L.size() <= R.size()) {
int value = *R.begin();
L_sum += value;
R_sum -= value;
L.insert(value);
R.erase(R.find(value));
}
}
void ins(int x) {
if (!L.empty() && x > *L.rbegin()) {
R.insert(x);
R_sum += x;
} else {
L_sum += x;
L.insert(x);
}
balance();
}
int get_med() {
return (L.empty() ? -1 : *L.rbegin());
}
lli get_cost() {
int med = get_med();
return (lli) L.size() * med - L_sum + R_sum - (lli) R.size() * med;
}
void reset() {
L.clear(); R.clear();
L_sum = R_sum = 0;
}
void solve() {
int K, N; cin >> K >> N;
vector <pair <int, int>> A;
lli ans = 0;
for (int i = 0; i < N; ++i) {
char P, Q;
int S, T;
cin >> P >> S >> Q >> T;
if (P == Q) {
ans += abs(S - T);
} else {
if (S > T) swap(S, T);
ans++; //cross bridge
A.emplace_back(S, T);
}
}
if (A.empty()) {
cout << ans << '\n';
return;
}
sort(A.begin(), A.end(), [&](pair <int, int> a, pair <int, int> b) {
return a.first + a.second < b.first + b.second;
});
//just calculate prefix answer and suffix answer
//if K == 1, it has to be prefix[N]
//if K == 2, then it will be min(prefix[i] + suffix[i + 1])
//we need to find median of the intersect segment
//for each segment that is outside the intersect range, it can be easily calculate by prefix sum
int siz = A.size();
vector <lli> prefix_ans(siz);
for (int i = 0; i < siz; ++i) {
ins(A[i].first); ins(A[i].second);
prefix_ans[i] = get_cost();
}
reset();
if (K == 1) {
ans += prefix_ans.back();
} else {
lli res = prefix_ans.back();
for (int i = siz - 1; i > 0; --i) {
ins(A[i].first); ins(A[i].second);
res = min(res, get_cost() + prefix_ans[i - 1]);
}
ans += res;
}
cout << ans << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
auto begin = std::chrono::high_resolution_clock::now();
#endif
int tt = 1;
while (tt--) {
solve();
}
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
return 0;
}
