#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, ll _x=0, int _i=0):
type(_type), x(_x), i(_i) {}
};
int k, n;
vector<ll> a, b, all;
vector<Event> events;
vector<pair<ll, int>> toB1;
vector<int> status;
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.at(i) - b1) + abs(b.at(i) - b1);
// toB1.emplace_back((distTo1 + a.at(i) + b.at(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.at(i) + b.at(i);
status.at(i) = 0;
}
for (; idxB2<2*n; idxB2++) {
ll b2 = all.at(idxB2);
// cout << b2 << ':' << '\n';
while (pt < 2*n and (events.at(pt).x < b2 or (events.at(pt).x == b2 and events.at(pt).type == 0))) {
int i = events.at(pt).i;
// if (status.at(i) == -1) {
// pt++;
// continue;
// }
if (events.at(pt).type == 0) {
res -= a.at(i) + b.at(i);
res += b.at(i) - a.at(i);
qtyb2-=2;
status.at(i) = 1;
} else {
res -= b.at(i) - a.at(i);
res += -a.at(i) - b.at(i);
qtyb2 -= 2;
status.at(i) = 2;
}
pt++;
}
// while (ptB1 < n and toB1.at(ptB1).first <= b2) {
// int i = toB1.at(ptB1).second;
// if (status.at(i) == 0) res -= a.at(i) + b.at(i);
// if (status.at(i) == 1) res -= b.at(i) - a.at(i);
// if (status.at(i) == 2) {
// res -= -a.at(i) - b.at(i);
// qtyb2 += 2;
// }
// res += abs(a.at(i) - b1) + abs(b.at(i) - b1);
// status.at(i) = -1;
// ptB1++;
// }
// cout << res << '\n';
ans = min(ans, res - b2*qtyb2);
while (pt < 2*n and events.at(pt).x == b2) {
int i = events.at(pt).i;
// if (status.at(i) == -1) {
// pt++;
// continue;
// }
res -= b.at(i) - a.at(i);
res += -a.at(i) - b.at(i);
qtyb2 -= 2;
status.at(i) = 2;
pt++;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> k >> n;
a = vector<ll>(n);
b = vector<ll>(n);
status = vector<int>(n);
ll base = 0;
for (int i=0; i<n; i++) {
char side1, side2;
cin >> side1 >> a.at(i) >> side2 >> b.at(i);
if (side1 == side2) {
base += abs(b.at(i) - a.at(i));
n--; i--;
continue;
}
if (a.at(i) > b.at(i)) swap(a.at(i), b.at(i));
all.push_back(a.at(i));
all.push_back(b.at(i));
events.push_back(Event(0, a.at(i), i));
events.push_back(Event(1, b.at(i), i));
}
sort(events.begin(), events.end(), cmp);
sort(all.begin(), all.end());
k = min(k, n);
if (k == 1) {
solve(0);
} else if (k == 2) {
for (int idxB1=0; idxB1 < 2*n-1; idxB1++) {
b1 = all.at(idxB1);
solve(idxB1+1);
}
} else ans = 0;
cout << base + ans << '\n';
return 0;
}
