/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <istream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif
struct segmentTree {
int N;
ll Null_val;
vector<ll> t;
segmentTree(int _n) {
t.resize(_n * 4);
N = _n;
Null_val = 0;
}
void build(int v, int l, int r, vector<int> &a) {
if (l == r) {
t[v] = a[l];
return;
}
int mid = (l + r) >> 1;
build((v << 1), l, mid, a);
build((v << 1) | 1, mid + 1, r, a);
t[v] = t[(v << 1)] + t[(v << 1) | 1];
}
void upd(int v, int l, int r, int &val, int &pos) {
if (l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
if (mid >= pos)
upd((v << 1), l, mid, val, pos);
else
upd((v << 1) | 1, mid + 1, r, val, pos);
t[v] = t[(v << 1)] + t[(v << 1) | 1];
}
ll ask(int v, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return t[v];
if (ql > r || l > qr)
return Null_val;
int mid = (l + r) >> 1;
return (ask((v << 1), l, mid, ql, qr) +
ask((v << 1) | 1, mid + 1, r, ql, qr));
}
};
struct node {
struct point {
int x, y;
};
point st, fs;
};
inline std::ostream &operator<<(std::ostream &os, const node &n) {
return os << "[St: (" << n.st.x << ", " << n.st.y << ") -> Fs: (" << n.fs.x << ", " << n.fs.y << ")]" << ln;
}
int _n, _k;
vector<node> V;
ll ans = INFll, sum = 0;
inline void systemd() {
sum = 0;
V.resize(_n);
}
ll calc(ll x) {
ll res = 0;
for (size_t i = 0; i < _n; i++) {
res += abs(V[i].st.y - x) + abs(V[i].fs.y - x);
}
return res;
}
void ternary_search() {
ans = INFll;
ll l = 0, r = INFi, res = -1;
while (l < r) {
int sz = (r - l + 1) / 3;
ll m1 = l + sz, m2 = r - sz;
ll al = calc(m1);
ll ar = calc(m2);
if (al < ar) {
r = m1 - 1;
res = m1;
} else if (al > ar) {
l = m2 + 1;
res = m2;
} else {
res = m1;
break;
}
}
myassert(res != -1, "WA: res is wrong");
ans = calc(res);
dbg(ans);
dbg(res);
}
char solve() {
if (!(cin >> _k >> _n))
return 1;
systemd();
for (size_t i = 0; i < _n; i++) {
char temp1, temp2;
int j1, j2;
cin >> temp1 >> j1 >> temp2 >> j2;
temp2 -= 'A';
temp1 -= 'A';
V[i].fs.x = temp2;
V[i].st.x = temp1;
V[i].fs.y = j2;
V[i].st.y = j1;
sum += abs(j1 - j2);
}
sort(V.begin(), V.end(), [&](const node &l, const node &r) {
return (l.fs.y - l.st.y) < (r.fs.y - r.st.y);
});
ternary_search();
cout << ans << ln;
return 0;
}
// Attack on titan<3
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t = 1e9;
// cin >> t;
for (int cases = 0; cases < t; cases++) {
if (solve())
break;
#ifdef ONPC
cerr << "__________\n";
#endif
}
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
