#line 1 "Palembang_Bridges.cpp"
#include <bits/stdc++.h>
#ifdef local
#define dbg(__VA_ARGS__) \
std::cerr << "[DBG|" << __LINE__ << "]: " << __VA_ARGS__ << std::endl;
#define cerr(__VA_ARGS__) std::cerr << __VA_ARGS__;
#else
#define dbg(...)
#define cerr(...)
#endif
template <class T> void vec_out(const std::vector<T> &cc) {
dbg("vector: ");
for (auto x : cc) {
cerr(x << " ");
}
cerr("\n");
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
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 (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;
}
