#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 5;
struct type {
char c1; int x1;
char c2; int x2;
} person[maxN];
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 ;
}
multiset<int> left1, right1, left2, right2;
long long sum_left1 = 0, sum_right1 = 0, sum_left2 = 0, sum_right2 = 0;
bool cmp(type a, type b) {
return (a.x1 + a.x2) < (b.x1 < b.x2);
}
void add_to_the_second(int i) {
right2.insert(person[i].x1);
right2.insert(person[i].x2);
sum_right2 += person[i].x1;
sum_right2 += person[i].x2;
int exchange = *right2.begin();
left2.insert(exchange);
right2.erase(right2.find(exchange));
sum_left2 += exchange;
sum_right2 -= exchange;
}
void delete_from_the_second(int i) {
int x1 = person[i].x1, x2 = person[i].x2;
int med_right = *right2.begin();
/// Erase x1 from the second set
if (x1 < med_right || right2.size() == 0) {
left2.erase(left2.find(x1));
sum_left2 -= x1;
}
else {
right2.erase(right2.find(x1));
sum_right2 -= x1;
}
med_right = (right2.size() > 0 ? *right2.begin() : 1e9 + 7);
/// Erase x2 from the second set
if (x2 < med_right) {
left2.erase(left2.find(x2));
sum_left2 -= x2;
}
else {
right2.erase(right2.find(x2));
sum_right2 -= x1;
}
if (left2.size() > right2.size()) {
auto it = left2.end(); it--;
int exchange = *it;
left2.erase(it);
right2.insert(exchange);
sum_left2 -= exchange;
sum_right2 += exchange;
}
else if (left2.size() < right2.size()) {
auto it = right2.begin();
int exchange = *it;
right2.erase(it);
left2.insert(exchange);
sum_left2 += exchange;
sum_right2 -= exchange;
}
}
void add_to_the_first(int i) {
int x1 = person[i].x1, x2 = person[i].x2;
right1.insert(x1);
right1.insert(x2);
sum_right1 += x1;
sum_right1 += x2;
int exchange = *right1.begin();
right1.erase(right1.find(exchange));
left1.insert(exchange);
sum_right1 -= exchange;
sum_left1 += exchange;
}
void subtask2() {
sort(person + 1, person + n + 1, cmp);
for (int i = 1; i <= n; i++)
add_to_the_second(i);
long long res = 1e18;
for (int i = 1; i <= n - 1; i++) {
delete_from_the_second(i);
add_to_the_first(i);
int median_first = *right1.begin();
int median_second = *right2.begin();
long long cal = (1LL * median_first * i - sum_left1) + (sum_right1 - 1LL * median_first * (1LL * i));
cal = cal + (1LL * median_second * (1LL * (n - i)) - sum_left2) + (sum_right2 - 1LL * median_second * (1LL * (n - i)));
res = min(res, cal);
}
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 (k == 1) subtask1();
else subtask2();
return 0;
}
