#include <bits/stdc++.h>
using namespace std;
#define task "15_bridge"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define ll long long
#define F first
#define S second
template<class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
}
return false;
}
typedef pair<int, int> ii;
int k, numCitizen;
vector<ii> citizen;
ll ans = 0;
namespace sub12 {
vector<int> pos;
void solve() {
int n = (int)citizen.size();
if (n == 0) {
cout << ans << "\n";
return;
}
FOR(i, 0, n - 1) {
pos.push_back(citizen[i].F);
pos.push_back(citizen[i].S);
}
sort(pos.begin(), pos.end());
n = pos.size();
int x = pos[n / 2];
ll res = 0;
for (ii p : citizen) {
res += 1LL * abs(x - p.F) + 1LL * abs(x - p.S);
}
cout << ans + res << "\n";
}
}
namespace sub3 {
vector<int> pos;
void solve() {
int n = (int)citizen.size();
if (n == 0) {
cout << ans << "\n";
return;
}
FOR(i, 0, n - 1) {
pos.push_back(citizen[i].F);
pos.push_back(citizen[i].S);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
ll res = LLONG_MAX;
for (int x : pos) {
for (int y : pos) {
if (x == y) continue;
ll cur = 0;
for (ii p : citizen) {
cur += min(abs(x - p.F) + abs(x - p.S), abs(y - p.F) + abs(y - p.S));
}
minimize(res, cur);
}
}
if (res == LLONG_MAX) res = 0;
cout << ans + res << "\n";
}
}
namespace sub45 {
bool cmp(ii &A, ii &B) {
return A.F + A.S < B.F + B.S;
}
priority_queue<int> leftPQ;
priority_queue<int, vector<int>, greater<int>> rightPQ;
ll leftSum = 0, rightSum = 0;
void insert(int x) {
int median = ((int)leftPQ.size() ? leftPQ.top() : 1000000001);
if (x < median) {
leftPQ.push(x);
leftSum += x;
}
else {
rightPQ.push(x);
rightSum += x;
}
if ((int)leftPQ.size() > (int)rightPQ.size() + 1) {
int val = leftPQ.top();
leftPQ.pop();
rightPQ.push(val);
leftSum -= val;
rightSum += val;
}
else if ((int)rightPQ.size() > (int)leftPQ.size()) {
int val = rightPQ.top();
rightPQ.pop();
leftPQ.push(val);
rightSum -= val;
leftSum += val;
}
}
ll pre[100005];
void solve() {
if ((int)citizen.size() == 0) {
cout << ans << "\n";
return;
}
sort(citizen.begin(), citizen.end(), cmp);
int n = (int)citizen.size();
FOR(i, 0, n - 1) {
insert(citizen[i].F);
insert(citizen[i].S);
pre[i + 1] = rightSum - leftSum;
}
ll res = LLONG_MAX;
while ((int)leftPQ.size()) leftPQ.pop();
while ((int)rightPQ.size()) rightPQ.pop();
leftSum = rightSum = 0;
FOD(i, n - 1, 0) {
insert(citizen[i].F);
insert(citizen[i].S);
minimize(res, rightSum - leftSum + pre[i]);
}
cout << ans + res << "\n";
}
}
int main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> k >> numCitizen;
FOR(i, 1, numCitizen) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if (a == b) ans += 1LL * abs(x - y);
else {
ans++;
citizen.push_back({x, y});
}
}
if (k == 1) sub12::solve();
else if (k == 2 && numCitizen <= 100) sub3::solve();
else sub45::solve();
return 0;
}
