#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 21, MOD = (int)1e9+7;
int n,k;
ll res = 0;
array<int,2> a[N];
ll L[N],R[N];
vector<pair<int,int>> sc;
void prec(){
for(int i = 1;i <= n;i++){
sc.push_back({a[i][0],0});
sc.push_back({a[i][1],1});
}
sort(sc.begin(),sc.end());
ll sum = 0,col = 0;
for(int i = 0;i < (int)sc.size();i++){
L[i] = (sc[i].first * 1ll * col) - sum;
if(sc[i].second == 1){
col++;
sum += sc[i].first;
}
}
col = sum =0 ;
for(int i = (int)sc.size() - 1;i >= 0;i--){
R[i] = sum - (sc[i].first * 1ll * col);
if(sc[i].second == 0){
col++;
sum += sc[i].first;
}
}
}
ll solve(){
if(!n) return 0;
ll res = 1e18;
for(int i = 0;i < (int)sc.size();i++){
res = min(res,2*(L[i] + R[i]));
}
return res;
}
ll calc(int l,int r){
ll sum = 0;
for(int i = 1;i <= n;i++){
if(a[i][0] > l && a[i][1] < r){
sum += min(2ll*(a[i][0] - l),2*1ll*(r - a[i][1]));
}
}
return sum;
}
vector<ll> clac(vector<int> x){
multiset<ll> _l,_r;
ll ls = 0,rs = 0;
vector<ll> ret((int)x.size());
auto add = [&](ll val)->void{
if(_l.empty()){
_l.insert(val);
ls += val;
return;
}
_l.insert(val);
ls += val;
val = (*_l.rbegin());
_l.erase(_l.find(val));
ls -= val;
_r.insert(val);
rs += val;
if((int)_r.size() > (int)_l.size()){
val = (*_r.begin());
_r.erase(_r.find(val));
rs -= val;
_l.insert(val);
ls += val;
}
};
for(int i = 0;i < (int)x.size();i++){
add(a[x[i]][0]);
add(a[x[i]][1]);
ll val = (*_l.rbegin());
ret[i] = val * 1ll * (ll)_l.size() - ls
+ rs - val * 1ll * (ll)_r.size();
// cout << rs << ' ' << ls << "x\n";
}
return ret;
}
void test() {
cin >> k >> n;
int _i = 0;
ll bf = 0;
for(int i = 1;i <= n;i++) {
char x,y;
int l,r;
cin >> x >> l >> y >> r;
if(l > r){
swap(l,r);
swap(x,y);
}
res += (r - l);
if(x == y){
bf += (r - l);
continue;
}
res++;
a[++_i] = {l,r};
}
n = _i;
prec();
if(k == 1){
cout << res + solve();
return;
}
if(n == 0){
cout << res;
return;
}
memset(L,0,sizeof(L));
memset(R,0,sizeof(R));
res = n;
vector<pair<double,int>> t;
for(int i = 1;i <= n;i++){
t.emplace_back((a[i][0] + a[i][1]) * 1.0 / 2.0,i);
}
sort(t.begin(),t.end());
vector<int> p;
for(auto [w,x]:t){
p.push_back(x);
// cout << a[x][0] << ' ' << a[x][1] << '\n';
}
vector<ll> A = clac(p);
reverse(p.begin(),p.end());
vector<ll> B = clac(p);
reverse(B.begin(),B.end());
// for(auto j:B){
// cout << j << '\n';
// }
// return;
ll mn = min(A.back(),B[0]);
for(int i = 0;i < (int)A.size() - 1;i++){
// cout << A[i] << ' ' << B[i + 1] << "x\n";
mn = min(mn,A[i] + B[i + 1]);
}
cout << mn + n +bf;
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
