#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
struct type {
char c1; int x1;
char c2; int x2;
} person[maxN];
bool cmp(type a, type b) {
return (a.x1 + a.x2) < (b.x1 + b.x2);
}
int k, n;
long long ans = 0;
void subtask1() {
vector<int> val;
for (int i = 1; i <= n; i++) {
val.push_back(person[i].x1);
val.push_back(person[i].x2);
}
sort(val.begin(), val.end());
int median = val[int(val.size() - 1) / 2];
//cout << median << '\n';
for (int i = 1; i <= n; i++)
ans += abs(person[i].x1 - median) + abs(person[i].x2 - median) + 1;
cout << ans;
return ;
}
void subtask2() {
sort(person + 1, person + n + 1, cmp);
long long res = 1e18;
vector<int> val1, val2;
for (int i = 1; i <= n - 1; i++) {
val1.clear();
val2.clear();
for (int j = 1; j <= i; j++) {
val1.push_back(person[j].x1);
val1.push_back(person[j].x2);
}
for (int j = i + 1; j <= n; j++) {
val2.push_back(person[j].x1);
val2.push_back(person[j].x2);
}
sort(val1.begin(), val1.end());
sort(val2.begin(), val2.end());
long long cal = 0;
int med1 = val1[int(val1.size() - 1) / 2], med2 = val2[int(val2.size() - 1) / 2];
for (auto v: val1)
cal = cal + abs(v - med1);
for (auto v: val2)
cal = cal + abs(v - med2);
res = min(res, cal);
}
cout << res + ans + n;
return ;
}
priority_queue<int> lhs;
priority_queue<int, vector<int>, greater<int>> rhs;
long long pre[maxN], lsum = 0, rsum = 0;
void add(int x) {
int median = (lhs.empty() ? 1000000007 : lhs.top());
if (x <= median) {
lhs.push(x);
lsum += x;
}
else {
rhs.push(x);
rsum += x;
}
if (lhs.size() > rhs.size() + 1) {
rhs.push(lhs.top());
rsum += lhs.top();
lsum -= lhs.top();
lhs.pop();
}
else if (lhs.size() < rhs.size()) {
lhs.push(rhs.top());
lsum += rhs.top();
rsum -= rhs.top();
rhs.pop();
}
}
void subtask3() {
sort(person + 1, person + n + 1, cmp);
for (int i = 1; i <= n; i++) {
add(person[i].x1);
add(person[i].x2);
pre[i] = rsum - lsum;
}
while (!lhs.empty()) lhs.pop();
while (!rhs.empty()) rhs.pop();
lsum = 0; rsum = 0;
long long res = pre[n];
for (int i = n; i >= 1; i--) {
add(person[i].x1);
add(person[i].x2);
res = min(res, pre[i - 1] + rsum - lsum);
}
cout << res + ans + n;
return ;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> k >> n;
for (int i = 1; i <= n; i++) {
char c1, c2;
int x1, x2;
cin >> c1 >> x1 >> c2 >> x2;
if (c1 == c2) {
ans = ans + abs(x1 - x2);
n--;
i--;
continue;
}
person[i] = {c1, x1, c2, x2};
}
if (n == 0) {
cout << ans;
return 0;
}
if (k == 1) subtask1();
else if (n <= 1000) subtask2();
else subtask3();
return 0;
}
