#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
long long unPuente(vector<int> & S, vector<int> & T) {
int N = (int) S.size();
if (N == 0) return 0;
vector<int> posiciones(2*N);
for (int i = 0; i < N; i++) {
posiciones[2*i] = S[i];
posiciones[2*i+1] = T[i];
}
sort(posiciones.begin(), posiciones.end());
long long int posicionPuente = (posiciones[N - 1] + posiciones[N])/2;
long long int total = (long long int) N;
for (int i = 0; i < N; i++) {
total += abs(S[i] - posicionPuente);
total += abs(T[i] - posicionPuente);
}
return total;
}
bool comparador(pair<int, int> a, pair<int, int> b) {
return a.first + a.second < b.first + b.second;
}
long long int sumaIzq, sumaDer;
void incluirEnLaMediana(int a, priority_queue<int> & pqIzq,
priority_queue<int, vector<int>, greater<int>> & pqDer) {
if (pqIzq.empty() || a <= pqIzq.top()) {
pqIzq.push(a);
sumaIzq += a;
} else {
pqDer.push(a);
sumaDer += a;
}
if (pqIzq.size() > pqDer.size() + 1) {
int valor = pqIzq.top();
pqIzq.pop();
sumaIzq -= valor;
pqDer.push(valor);
sumaDer += valor;
} else if (pqIzq.size() < pqDer.size()) {
int valor = pqDer.top();
pqIzq.push(valor);
sumaIzq += valor;
pqDer.pop();
sumaDer -= valor;
}
}
long long int dosPuentes(vector<int> & S, vector<int> & T) {
int N = (int) S.size();
if (N == 0) return 0;
vector<pair<int, int>> posiciones(N);
for (int i = 0; i < N; i++) {
posiciones[i] = make_pair(S[i], T[i]);
}
sort(posiciones.begin(), posiciones.end(), comparador);
priority_queue<int> pqIzq;
priority_queue<int, vector<int>, greater<int>> pqDer;
sumaIzq = 0, sumaDer = 0;
vector<long long int> prefSumas(N);
for (int i = 0; i < N; i++) {
incluirEnLaMediana(posiciones[i].first, pqIzq, pqDer);
incluirEnLaMediana(posiciones[i].second, pqIzq, pqDer);
prefSumas[i] = sumaDer - sumaIzq;
}
long long int mejorPosible = prefSumas[N-1];
pqIzq = priority_queue<int>();
pqDer = priority_queue<int, vector<int>, greater<int>>();
sumaIzq = 0;
sumaDer = 0;
for (int i = N-1; i > 0; i--) {
incluirEnLaMediana(posiciones[i].first, pqIzq, pqDer);
incluirEnLaMediana(posiciones[i].second, pqIzq, pqDer);
mejorPosible = min(mejorPosible, sumaDer - sumaIzq + prefSumas[i-1]);
}
incluirEnLaMediana(posiciones[0].first, pqIzq, pqDer);
incluirEnLaMediana(posiciones[0].second, pqIzq, pqDer);
mejorPosible = min(mejorPosible, sumaDer - sumaIzq);
return mejorPosible+N;
}
int main() {
int K, N;
cin >> K >> N;
vector<int> S, T;
long long int mismoLado = 0;
for (int i = 0; i < N; i++) {
char lado1, lado2;
int pos1, pos2;
cin >> lado1 >> pos1 >> lado2 >> pos2;
if (lado1 == lado2) {
mismoLado += abs(pos1-pos2);
} else {
S.push_back(pos1);
T.push_back(pos2);
}
}
if (K == 1) {
cout << mismoLado + unPuente(S, T) << '\n';
} else {
cout << mismoLado + dosPuentes(S, T) << '\n';
}
return 0;
}
