#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
// Ask for sum 1 -> n for full (one based indexing)
class BIT {
private: vector<ll> ct; int n;
int LSOne(int x) {
return x&(-x);
}
public:
BIT(int x) {
n = x;
ct.resize(n+1);
}
ll sum(int a) {
ll sum = 0;
for (; a > 0; a -= LSOne(a)) sum += ct[a];
return sum;
}
ll sum(int a, int b) {
return sum(b) - (a == 1 ? 0 : sum(a-1));
}
void update(int p, ll v) {
for (; p < n+1; p += LSOne(p)) ct[p] += v;
}
};
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int k, n; cin >> k >> n;
ll init = 0;
vector<vector<ll>> pts; // {point; -1 -> start, 1 -> end; other end point}
vector<ii> seg;
map<int, int> ptToId;
vector<ll> idToPt(1);
for_(i, 0, n) {
char za, zb; int a, b; cin >> za >> a >> zb >> b;
if (b < a) {
swap(za, zb);
swap(a, b);
}
if (za != zb) {
seg.push_back({a, b});
ptToId[a] = ptToId[b] = 0;
init++;
} else init += b-a;
}
int pt = 1;
for (auto i: ptToId) {
ptToId[i.first] = pt++;
idToPt.push_back(i.first);
}
for (auto i: seg) {
int x = ptToId[i.first], y = ptToId[i.second];
pts.push_back({x, -1, y});
pts.push_back({y, 1, x});
}
sort(pts.begin(), pts.end());
if (k == 1) {
for (auto i: pts) init += abs(idToPt[i[0]]-idToPt[pts[pts.size()/2][0]]);
cout << init << endl;
return 0;
}
BIT sum(pt+1), ct(pt+1);
for (auto i: pts) {
ct.update(i[0], 1);
sum.update(i[0], idToPt[i[0]]);
}
ll mn = LONG_LONG_MAX;
ll curr = 0;
for (auto i: pts) {
// for (int j: i) cout << j << " ";
// cout << endl;
ct.update(i[0], i[1]);
ct.update(i[2], i[1]);
sum.update(i[0], i[1]*idToPt[i[0]]);
sum.update(i[2], i[1]*idToPt[i[2]]);
curr += (-i[1]) * abs(idToPt[i[0]]-idToPt[i[2]]);
if (i[1] == -1) {
int l = 1, r = pt+1, ans = 1;
while (l < r) {
int mid = (l+r)/2;
ll ls = ct.sum(mid), rs = ct.sum(mid+1, pt);
if (ls >= rs) {
ans = r = mid;
} else l = mid+1;
}
// cout << ans << " " << curr << endl;
// cout << "left : " << sum.sum(ans) << " right: " << sum.sum(ans+1, pt+1) << endl;
mn = min(mn, idToPt[ans]*(ct.sum(ans)-ct.sum(ans+1, pt)) - sum.sum(ans) + sum.sum(ans+1, pt) + curr);
}
}
cout << init+mn << endl;
return 0;
}
