#line 1 "Palembang_Bridges.cpp"
#include <bits/stdc++.h>
#define int std::int64_t
#ifdef local
#define dbg(__VA_ARGS__) \
std::cerr << "[DBG|" << __LINE__ << "]: " << __VA_ARGS__ << std::endl;
#define cerr(__VA_ARGS__) std::cerr << __VA_ARGS__;
template <class T> void vec_out(const std::vector<T> &cc) {
dbg("vector: ");
for (auto x : cc) {
cerr(x << " ");
}
cerr("\n");
}
#else
#define dbg(...)
#define cerr(...)
template <class T> void vec_out(const std::vector<T> &cc) {}
#endif
using namespace std;
using ll = long long;
const int mod = ll(1e9) + 7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in
// c++ its -1 but its suppose to be 10^9+6
const int N = ll(2e5) + 100;
const long long inf = 5e18;
int k, n, m;
pair<int, int> point[N];
#define ff first
#define ss second
bool cmp(pair<int, int> a, pair<int, int> b) {
return (a.ff + a.ss) < (b.ff + b.ss);
}
#define all(a) a.begin(), a.end()
#define pb push_back
vector<int> get(int l, int r) {
if (l > r)
return {};
vector<int> res;
for (int i = l; i <= r; i++)
res.pb(point[i].ff), res.pb(point[i].ss);
sort(all(res));
return res;
}
std::int32_t main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> k >> n;
long long ex = 0;
for (int i = 1; i <= n; i++) {
char p, q;
int s, t;
cin >> p >> s >> q >> t;
if (s > t)
swap(s, t);
if (p == q)
ex += t - s;
else {
ex++;
point[++m] = {s, t};
}
}
sort(point + 1, point + m + 1, cmp);
long long ans = 0;
if (k == 1) {
vector<int> pos = get(1, m);
int mid = (pos.size()) / 2;
for (auto x : pos)
ans += abs(pos[mid] - x);
} else if (k == 2 && m) {
ans = inf;
for (int i = 1; i <= m; i++) {
vector<int> pos1 = get(1, i), pos2 = get(i + 1, m);
int mid1 = (pos1.size()) / 2, mid2 = (pos2.size()) / 2;
long long res = 0;
for (auto x : pos1)
res += abs(pos1[mid1] - x);
for (auto x : pos2)
res += abs(pos2[mid2] - x);
ans = min(ans, res);
}
}
cout << ans + ex;
/*
int K, N;
std::cin >> K >> N;
std::vector<std::tuple<char, std::int64_t, char, std::int64_t>> PSQT(N);
for (auto &[P, S, Q, T] : PSQT) {
std::cin >> P >> S >> Q >> T;
}
std::int64_t ans = 0;
std::vector<std::pair<std::int64_t, std::int64_t>> HW;
for (auto [P, S, Q, T] : PSQT) {
if (S > T) {
std::swap(S, T);
}
if (P == Q) {
ans += std::abs(T - S);
continue;
}
// the roads
ans++;
HW.emplace_back(S, T);
}
std::sort(HW.begin(), HW.end(), [](const auto &x, const auto &y) {
return (x.first + x.second) < (y.first + y.second);
});
auto calc = [&](std::int64_t S, std::int64_t T, std::int64_t x) {
return std::abs(S - x) + std::abs(T - x) + 1;
};
auto get = [&](int l, int r) {
if (l > r) {
return std::vector<std::int64_t>{};
}
std::vector<std::int64_t> pts;
for (int i = l; i <= r; i++) {
auto &&[H, W] = HW[i];
pts.push_back(H);
pts.push_back(W);
}
std::sort(pts.begin(), pts.end());
return pts;
};
if (K == 1) {
// find median as that is optimal for the
// for all sum abs(S - x) + abs(T - x)
auto pts = get(0, HW.size() - 1);
auto mid = pts.size() / 2;
mid--;
for (auto x : pts) {
ans += std::abs(x - pts[mid]);
}
std::cout << ans << "\n";
return 0;
}
// split at some point i
// then using same median technique as in K = 1
// then we get 2 sub vectors => in each find median (still optimal) and then
// add them up, thus giving you the 2 bridges
std::int64_t res = LLONG_MAX;
for (int f = 0; f < HW.size(); f++) {
auto fir = get(0, f);
auto sec = get(f + 1, HW.size() - 1);
if (fir.empty() || sec.empty()) {
continue;
}
vec_out(fir);
vec_out(sec);
auto m0 = fir.size() / 2;
m0--;
auto m1 = sec.size() / 2;
m1--;
auto md0 = fir[m0];
auto md1 = fir[m1];
std::int64_t tmp = 0;
// for (auto [H, W] : HW) {
// tmp += std::min(calc(H, W, md0), calc(H, W, md1));
// }
for (auto x : fir) {
tmp += std::abs(x - fir[m0]);
}
for (auto x : sec) {
tmp += std::abs(x - sec[m1]);
}
res = std::min(res, tmp);
}
ans += res;
std::cout << ans << "\n";
*/
return 0;
}
