#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'
#define MAXN 1050
int k, n;
int z1[MAXN], z2[MAXN], lft[MAXN], rgt[MAXN];
ll ans, sig;
vector<int> cor;
vector<int> beg[2 * MAXN], fin[2 * MAXN];
vector<int> goback[2 * MAXN];
int32_t main(void)
{
fast_io;
cin >> k >> n;
FOR(i, 0, n)
{
char c;
cin >> c;
z1[i] = c - 'A';
cin >> lft[i] >> c;
z2[i] = c - 'A';
cin >> rgt[i];
if (lft[i] > rgt[i]) swap(lft[i], rgt[i]);
ans += rgt[i] - lft[i] + (z1[i] != z2[i]);
cor.pb(lft[i]);
cor.pb(rgt[i]);
sig += lft[i];
}
dbgr(z1, z1 + n);
dbgr(z2, z2 + n);
ll bksum = 0, bkcnt = 0;
ll fwsum = 0, fwcnt = 0;
sort(all(cor));
cor.resize(unique(all(cor)) - cor.begin());
FOR(i, 0, n)
{
lft[i] = lower_bound(all(cor), lft[i]) - cor.begin();
rgt[i] = lower_bound(all(cor), rgt[i]) - cor.begin();
if (z1[i] == z2[i]) continue;
beg[lft[i]].pb(i);
fin[rgt[i]].pb(i);
fwsum += cor[lft[i]];
fwcnt++;
}
FOR(i, 0, (int)cor.size())
{
for (int u : beg[i])
{
fwcnt--;
fwsum -= cor[lft[u]];
dbg(u);
}
/* if (i == 4)
{
dbg(bkcnt);
dbg(fwcnt);
dbg(bksum);
dbg(fwsum);
dbg(cor[i]);
}*/
sig = min(sig, cor[i] * bkcnt - bksum + fwsum - cor[i] * fwcnt);
if (k == 2)
{
ll res = LINF;
ll _fwsum = fwsum, _fwcnt = fwcnt;
ll midsum = 0, midcnt = 0;
ll midbksum = 0;
FOR(j, i + 1, (int)cor.size())
{
for (int u : beg[j])
{
fwcnt--;
fwsum -= cor[lft[u]];
}
for (int u : goback[j])
{
midbksum += cor[lft[u]] - cor[i];
midcnt--;
midsum -= cor[rgt[u]];
}
res = min(res, midbksum + cor[j] * midcnt - midsum + fwsum - cor[j] * fwcnt);
for (int u : fin[j]) if (lft[u] > i)
{
midcnt++;
midsum += cor[rgt[u]];
// assign go back
int pos = lower_bound(all(cor), cor[rgt[u]] + cor[lft[u]] - cor[i]) - cor.begin();
if (pos < (int)cor.size())
goback[pos].pb(u);
}
}
FOR(j, 0, 2 * MAXN) goback[j].clear();
fwsum = _fwsum;
fwcnt = _fwcnt;
res += cor[i] * bkcnt - bksum;
sig = min(sig, res);
}
for (int u : fin[i])
{
bkcnt++;
bksum += cor[rgt[u]];
}
}
ans += 2 * sig;
cout << ans << endl;
return 0;
}
