#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Cay ngay cay dem nhung deo duoc cong nhan
*/
const ll oo = 2e18;
int k, n;
vpi a;
ll tv = 0, rs = oo;
namespace subtask1 {
void solve() {
vi b;
FOR(i, 1, n) {
b.pb(a[i].st);
b.pb(a[i].nd);
}
EACH(i, b) {
ll sum = 0;
FOR(j, 1, n)
if (a[j].nd <= i) sum += 2 * i - a[j].st - a[j].nd + 1;
else if (a[j].st >= i) sum += a[j].st + a[j].nd - 2 * i + 1;
else sum += a[j].nd - a[j].st + 1;
rs = min(rs, sum);
}
cout << tv + rs;
}
}
namespace subtask2 {
const int N = 2e5 + 5;
int prec[N], sufc[N];
ll pres[N], sufs[N];
bool cmp(pi &a, pi &b) { return a.nd < b.nd; }
bool cmp1(pi &a, pi &b) { return a.st > b.st; }
void solve() {
FOR(i, 1, n) tv += a[i].nd - a[i].st + 1;
vi b;
FOR(i, 1, n) {
b.pb(a[i].st);
b.pb(a[i].nd);
}
sort(a.begin() + 1, a.end(), cmp);
sort(all(b));
int l = 1, cnt = 0;
ll sum = 0;
FOR(i, 0, sz(b) - 1) {
int x = b[i];
WHILE(l <= n && a[l].nd < x) {
++cnt;
sum += 2 * a[l].nd;
++l;
}
prec[i] = cnt;
pres[i] = sum;
}
sort(a.begin() + 1, a.end(), cmp1);
l = 1;
cnt = 0;
sum = 0;
FOS(i, sz(b) - 1, 0) {
int x = b[i];
WHILE(l <= n && a[l].st > x) {
++cnt;
sum += 2 * a[l].st;
++l;
}
sufc[i] = cnt;
sufs[i] = sum;
}
FOR(i, 0, sz(b) - 1) {
int x = b[i];
rs = min(rs, 2LL * x * prec[i] - pres[i] + sufs[i] - 2LL * x * sufc[i]);
}
cout << tv + rs;
}
}
namespace subtask3 {
void solve() {
vi b;
FOR(i, 1, n) {
b.pb(a[i].st);
b.pb(a[i].nd);
}
sort(all(b));
FOR(i, 0, sz(b) - 1)
FOR(j, i, sz(b) - 1) {
int x = b[i], y = b[j];
ll sum = 0;
FOR(z, 1, n)
if (a[z].nd < x) sum += 2 * x - a[z].st - a[z].nd + 1;
else if (a[z].st > y) sum += a[z].st + a[z].nd - 2 * y + 1;
else if (x < a[z].st && a[z].nd < y) sum += min(a[z].st + a[z].nd - 2 * x + 1, 2 * y - a[z].st - a[z].nd + 1);
else sum += a[z].nd - a[z].st + 1;
rs = min(rs, sum);
}
cout << tv + rs;
}
}
namespace subtask4 {
#define int long long
const int N = 2005;
pll f[N];
vi b;
void upd(int ps, pi v) {
++ps;
for (int i = ps; i < N; i += (i & -i)) {
f[i].st += v.st;
f[i].nd += v.nd;
}
}
void upd(int l, int r, pi v) {
upd(l, {v.nd, v.st - l * v.nd});
upd(r + 1, {-v.nd, -v.st + l * v.nd});
}
pll get(int ps) {
++ps;
pll rs = {0, 0};
for (int i = ps; i > 0; i -= (i & -i)) {
rs.st += f[i].st;
rs.nd += f[i].nd;
}
return rs;
}
ll getv(int ps) {
pll cur = get(ps);
return cur.st * b[ps] + cur.nd;
}
void updr(int l, int r, pi v) {
if (l > r || l > b.back()) return;
int ps1 = lb(all(b), l) - b.begin(), ps2;
if (b.back() <= r) ps2 = sz(b) - 1;
else ps2 = ub(all(b), r) - b.begin() - 1;
if (ps1 > ps2) return;
upd(ps1, ps2, {v.st + (b[ps1] - l) * v.nd, v.nd});
}
void solve() {
FOR(i, 1, n) {
b.pb(a[i].st);
b.pb(a[i].nd);
}
sort(all(b));
FOR(i, 0, sz(b) - 1) {
FOR(j, 0, N - 1) f[j] = {0, 0};
int x = b[i];
ll sum = 0;
FOR(j, 1, n)
if (a[j].nd < x) sum += 2 * x - a[j].st - a[j].nd + 1;
else if (a[j].st <= x) sum += a[j].nd - a[j].st + 1;
else {
updr(0, a[j].st - 1, {a[j].st + a[j].nd + 1, -2});
updr(a[j].st, a[j].nd, {a[j].nd - a[j].st + 1, 0});
// debug(a[j].st, a[j].nd);
updr(a[j].nd + 1, a[j].nd + a[j].st - x, {2 + a[j].nd - a[j].st + 1, 2});
updr(a[j].nd + a[j].st - x + 1, b.back(), {a[j].st + a[j].nd - 2 * x + 1, 0});
}
FOR(j, i, sz(b) - 1) {
// int y = b[j];
// debug(x, y, sum, getv(j));
rs = min(rs, sum + getv(j));
}
// cerr << "\n\n";
}
cout << tv + rs;
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> k >> n;
a.pb({0, 0});
FOR(i, 1, n) {
char p, q;
int s, t;
cin >> p >> s >> q >> t;
if (p == q) tv += abs(s - t);
else a.pb({min(s, t), max(s, t)});
}
n = sz(a) - 1;
if (n == 0) {
cout << tv;
return 0;
}
if (k == 1 && n <= 1e3) {
subtask1::solve();
return 0;
}
if (k == 1 && n <= 1e5) {
subtask2::solve();
return 0;
}
if (k == 2 && n <= 1e2) {
subtask3::solve();
return 0;
}
if (k == 2 && n <= 1e3) {
subtask4::solve();
return 0;
}
return 0;
}
/*
2 2
A 5 B 5
A 0 B 4
*/
