#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
const int maxnk = 310004;
ll dbuf[maxnk];
ll *d[maxnk];
vector<pii> coords;
vector<pii> v;
namespace Set {
int t[maxnk * 2];
int base = 1;
void init() {
base = 1;
while (base < sz(coords))
base *= 2;
fill(t, t + 2 * base, 0);
}
void put(int v, int val) {
v += base;
t[v] = val;
while (v > 1) {
v /= 2;
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
int prev(int v) {
v += base;
while (true) {
int u = v;
v /= 2;
if ((u & 1) && t[u] != t[v]) {
v *= 2;
break;
}
}
while (v < base) {
v *= 2;
if (t[v + 1] > 0)
++v;
}
return v - base;
}
int next(int v) {
v += base;
while (true) {
int u = v;
v /= 2;
if (!(u & 1) && t[u] != t[v]) {
v = v * 2 + 1;
break;
}
}
while (v < base) {
v *= 2;
if (t[v] == 0)
++v;
}
return v - base;
}
}
namespace T {
int bl, br;
int pos;
ll f;
void init(int id) {
Set::init();
bl = id, br = id + 1;
Set::put(v[id].first, 1);
Set::put(v[id].second, 1);
pos = v[id].second;
f = coords[v[id].second].first - coords[v[id].first].first;
}
void move(int to) {
f += (coords[to].first - coords[pos].first) * 2;
pos = to;
}
void ins(int id) {
//cerr << "ins " << id << '\n';
int l = v[id].first;
int r = v[id].second;
Set::put(l, 1);
Set::put(r, 1);
f += abs(coords[r].first - coords[pos].first);
f += abs(coords[l].first - coords[pos].first);
if (pos < l)
pos = Set::next(pos);
else if (r < pos)
move(Set::prev(pos));
}
void del(int id) {
//cerr << "del " << id << '\n';
int l = v[id].first;
int r = v[id].second;
if (pos <= l)
pos = Set::prev(pos);
else if (r <= pos)
move(Set::next(pos));
Set::put(l, 0);
Set::put(r, 0);
f -= abs(coords[r].first - coords[pos].first);
f -= abs(coords[l].first - coords[pos].first);
}
void moveBounds(int nl, int nr) {
//cerr << "move " << nl << ' ' << nr << '\n';
assert(nl < nr);
while (br < nr)
ins(br++);
while (bl > nl)
ins(--bl);
while (br > nr)
del(--br);
while (bl < nl)
del(bl++);
assert(bl == nl && br == nr);
}
} //T
int ck;
void divideAndConquer(int l, int r, int pl, int pr) {
assert(T::bl == pl && T::br == l);
int mid = (l + r) / 2;
int pm = pl;
T::moveBounds(pm, mid);
pair<ll, int> best{T::f + d[ck][pm], pm};
for (pm = pl + 1; pm < min(mid, pr); ++pm) {
T::moveBounds(pm, mid);
best = min(best, {T::f + d[ck][pm], pm});
}
d[ck + 1][mid] = best.first, pm = best.second;
if (mid + 1 < r) {
T::moveBounds(pm, mid + 1);
divideAndConquer(mid + 1, r, pm, pr);
}
T::moveBounds(pl, l);
if (l < mid)
divideAndConquer(l, mid, pl, pm + 1);
}
long long ttt,nn;
char c1,c2;
int main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
#else
#endif
int n, k;
cin >> k >> n;
forn (i, k + 1)
d[i] = dbuf + i * (n + 1);
vector<pii> _v;
forn (i, n) {
int l, r;
cin >> c1 >> l >> c2 >> r;
if (l > r)
swap(l, r);
if(c1 == c2) { ttt += r-l; continue; }
ttt++;
nn++;
_v.emplace_back(l, r);
}
n = nn;
sort(_v.begin(), _v.end(), [](pii a, pii b) {
return a.first + a.second < b.first + b.second;
});
forn (i, n) {
coords.emplace_back(_v[i].first, i * 2);
coords.emplace_back(_v[i].second, i * 2 + 1);
}
sort(coords.begin(), coords.end());
v.resize(n);
forn (i, n) {
v[i].first = lower_bound(coords.begin(), coords.end(),
pii{_v[i].first, i * 2}) - coords.begin();
v[i].second = lower_bound(coords.begin(), coords.end(),
pii{_v[i].second, i * 2 + 1}) - coords.begin();
}
forn (i, k + 1)
fill(d[i], d[i] + n + 1, infl);
d[0][0] = 0;
forn (j, k) {
T::init(0);
ck = j;
divideAndConquer(1, n + 1, 0, n);
}
cout << ttt + d[k][n] << '\n';
}
