/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
ll solv(vector<array<ll, 2>> &a){
if(a.size() == 0) return 0ll;
vector<pair<ll, ll>> v;
for(int i = 0; i < a.size(); ++i) v.pb({a[i][0], 0}), v.pb({a[i][1], 1});
sort(all(v));
vector<pair<ll, ll>> pref(v.size());
vector<pair<ll, ll>> suf(v.size());
pref[0] = {0, 0};
for(int i = 1; i < v.size(); ++i){
pref[i] = pref[i - 1];
if(v[i].second == 1) pref[i].first += v[i].first, pref[i].second++;
}
suf[v.size() - 1] = {0, 0};
for(int i = v.size() - 2; i >= 0; --i){
suf[i] = suf[i + 1];
if(v[i].second == 0) suf[i].first += v[i].first, suf[i].second++;
}
ll best = 1e18;
for(int i = 0; i < v.size(); ++i){
if(abs(suf[i].second - pref[i].second) <= 1)
best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
}
return best*2 + a.size();
}
int k, n;
ll ans = 0;
pair<ll, ll> pref[N], suf[N];
array<ll, 2> a[N];
vector<int> L[N];
set<int> R[N];
void solve(){
cin >> k >> n;
int c = 0;
for(int i = 1; i <= n; ++i){
char c1, c2; ll x1, x2; cin >> c1 >> x1 >> c2 >> x2;
if(c1 == c2){
ans += abs(x1-x2);
}else{
++c;
a[c][0] = min(x1, x2);
a[c][1] = max(x1, x2);
ans += abs(x1-x2);
// cout << a[c][0] << ' '<< a[c][1] << '\n';
}
}
n = c;
if(n==0){
cout << ans;
return;
}
sort(a+1, a+1+n);
vector<pair<ll, ll>> v;
for(int i = 1; i <= n; ++i) v.pb({a[i][0], 0}), v.pb({a[i][1], 1});
sort(all(v));
pref[0] = {0, 0};
for(int i = 1; i < v.size(); ++i){
pref[i] = pref[i - 1];
if(v[i].second == 1) pref[i].first += v[i].first, pref[i].second++;
}
suf[v.size() - 1] = {0, 0};
for(int i = v.size() - 2; i >= 0; --i){
suf[i] = suf[i + 1];
if(v[i].second == 0) suf[i].first += v[i].first, suf[i].second++;
}
if(k == 1){
ll best = 1e18;
for(int i = 0; i < v.size(); ++i){
if(abs(suf[i].second - pref[i].second) <= 1)
best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
}
cout << ans + best*2 + n;
}else{
ll best = 1e18;
for(int i = 0; i <= n; ++i){
vector<array<ll, 2>> A, B;
for(int j = 1; j <= i; ++j) A.pb(a[i]);
for(int j = i+1; j <= n; ++j) B.pb(a[i]);
best = min(best, solv(A) + solv(B));
}
cout << ans + best;
return;
suf[2*n] = {0, 0};
for(int i = 0; i < v.size(); ++i) R[pref[i].second - suf[i].second + M].insert(i);
for(int i = 0; i < v.size(); ++i){
if(abs(suf[i].second - pref[i].second) <= 1)
best = min(best, suf[i].first - pref[i].first + (v[i].first * pref[i].second) - (v[i].first * suf[i].second));
}
for(int i = 0; i < v.size(); ++i){
int x = pref[i].second - suf[i].second + M;
L[x].pb(i);
R[x].erase(i);
int y = suf[i + 1].second;
int y2 = -pref[i].second;
for(int j = y + M - 2; j <= y + M + 2; ++j){
for(int j2 = y2 + M - 2; j2 <= y2 + M + 2; ++j2){
for(auto l: L[j]){
for(auto r: R[j2]){
best = min(best,
(suf[l].first - suf[i + 1].first) - pref[l].first + (pref[l].second - (suf[l].second - suf[i + 1].second)) * v[l].first +
suf[r].first - (pref[r].first - pref[i].first) + ((pref[r].second - pref[i].second) - suf[r].second) * v[r].first
);
}
}
}
}
}
cout << ans + 2*best + n;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
