#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
const ll INF = 1e10;
const ll INFLL = 1e18;
struct Event {
int type; ll x; int i; // 0: open 1: close
Event(int _type=0, int _x=0, int _i=0):
type(_type), x(_x), i(_i) {}
};
int k, n;
ll a[MAXN], b[MAXN], all[2*MAXN];
Event events[2*MAXN];
vector<pair<ll, int>> toB1;
int status[MAXN];
ll ans = INFLL, b1 = -INF;
bool cmp(Event a, Event b) {
if (a.x == b.x) {
return a.type < b.type;
}
return a.x < b.x;
}
void solve(int idxB2) {
int pt = 0, ptB1 = 0;
for (int i=0; i<n; i++) {
ll distTo1 = abs(a[i] - b1) + abs(b[i] - b1);
toB1.emplace_back((distTo1 + a[i] + b[i] + 1) / 2, i);
}
sort(toB1.begin(), toB1.end());
ll res = n; ll qtyb2 = 2*n;
for (int i=0; i<n; i++) {
res += a[i] + b[i];
status[i] = 0;
}
for (; idxB2<2*n; idxB2++) {
ll b2 = all[idxB2];
// cout << b2 << ':' << '\n';
while (pt < 2*n and (events[pt].x < b2 or (events[pt].x == b2 and events[pt].type == 0))) {
int i = events[pt].i;
if (status[i] == -1) {
pt++;
continue;
}
if (events[pt].type == 0) {
res -= a[i] + b[i];
res += b[i] - a[i];
qtyb2-=2;
status[i] = 1;
} else {
res -= b[i] - a[i];
res += -a[i] - b[i];
qtyb2 -= 2;
status[i] = 2;
}
pt++;
}
while (ptB1 < n and toB1[ptB1].first <= b2) {
int i = toB1[ptB1].second;
if (status[i] == 0) res -= a[i] + b[i];
if (status[i] == 1) res -= b[i] - a[i];
if (status[i] == 2) {
res -= -a[i] - b[i];
qtyb2 += 2;
}
res += abs(a[i] - b1) + abs(b[i] - b1);
status[i] = -1;
ptB1++;
}
// cout << res << '\n';
ans = min(ans, res - b2*qtyb2);
while (pt < 2*n and events[pt].x == b2) {
int i = events[pt].i;
if (status[i] == -1) {
pt++;
continue;
}
res -= b[i] - a[i];
res += -a[i] - b[i];
qtyb2 -= 2;
status[i] = 2;
pt++;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> k >> n;
ll base = 0;
for (int i=0; i<n; i++) {
char side1, side2;
cin >> side1 >> a[i] >> side2 >> b[i];
if (side1 == side2) {
base += abs(b[i] - a[i]);
n--; i--;
continue;
}
if (a[i] > b[i]) swap(a[i], b[i]);
all[2*i] = a[i];
all[2*i+1] = b[i];
events[2*i] = Event(0, a[i], i);
events[2*i+1] = Event(1, b[i], i);
}
sort(events, events+2*n, cmp);
sort(all, all+2*n);
k = min(k, n);
if (k == 1) {
solve(0);
} else {
for (int idxB1=0; idxB1 < 2*n-1; idxB1++) {
b1 = all[idxB1];
solve(idxB1+1);
}
}
cout << base + ans << '\n';
return 0;
}
