#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
map<int,int> whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem;
struct SegTree{
vector<pair<int,int>> segtree;
SegTree(int n){
segtree.resize(tol(ceil(log2(n)+1))-1,{0,0});
}
void push(int x){
int l = 0, r = segtree.size()/2;
int node = 0;
int pos = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
while (l<r){
int mid = l+(r-l)/2;
segtree[node].first+=x;
segtree[node].second++;
if (l==r) break;
if (mid>=pos){
r=mid;
node=node*2+1;
}
else {
l=mid+1;
node=node*2+2;
}
}
segtree[node].first+=x;
segtree[node].second++;
}
void erase(int x){
int l = 0, r = segtree.size()/2;
int node = 0;
int pos = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
while (l<r){
int mid = l+(r-l)/2;
segtree[node].first-=x;
segtree[node].second--;
if (l==r) break;
if (mid>=pos){
r=mid;
node=node*2+1;
}
else {
l=mid+1;
node=node*2+2;
}
}
segtree[node].first-=x;
segtree[node].second--;
}
int median(){
int l = 0, r = segtree.size()/2;
int node = 0;
int k = segtree[node].second/2;
while (l<r){
int mid = l+(r-l)/2;
int left = segtree[node*2+1].second;
if (left>=k){
node=node*2+1;
r=mid;
}
else {
k-=left;
node=node*2+2;
l=mid+1;
}
}
return l;
}
pair<int,int> query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1){
r=segtree.size()/2, node=0;
}
if (l>=tarl && r<=tarr) return segtree[node];
if (l>tarr || r<tarl) return {0,0};
int mid = l+(r-l)/2;
pair<int,int> lnode = query(tarl, tarr, l, mid, node*2+1);
pair<int,int> rnode = query(tarl, tarr, mid+1, r, node*2+2);
return {lnode.first+rnode.first,lnode.second+rnode.second};
}
};
int LIMN;
vector<int> compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz;
struct Solution{
SegTree segtree,ls,rs;
Solution():segtree(LIMN),ls(LIMN),rs(LIMN){}
void push(int l, int r){
ls.push(l);
rs.push(r);
segtree.push(l);
segtree.push(r);
}
void erase(int l, int r){
ls.erase(l);
rs.erase(r);
segtree.erase(l);
segtree.erase(r);
}
int query(){
int x = compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz[segtree.median()];
int pl = whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[x];
pair<int,int> left = rs.query(0,pl);
pair<int,int> right = ls.query(pl,LIMN-1);
return (left.second*x-left.first+right.first-right.second*x)*2;
}
};
int32_t main(){
ios;
int t=1;
int tno = 0;
if (!t) cin>>t;
while (t-(tno++)){
deci(k);deci(n);
LIMN = 2*n;
vector<pair<int,int>> segment;
int ans = 0;
for (int i = 0; i < n; i++){
char a,c;
int b,d;
cin>>a>>b>>c>>d;
ans+=abs(b-d);
if (a!=c){
ans++;
segment.push_back({min(b,d),max(b,d)});
compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.push_back(b);
compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.push_back(d);
}
}
sortarr(compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz);
for (int i = 0; i < compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz.size(); i++){
whatthefuckneyapionuzabisizdunyayaasirisinirlendimbunebicimproblem[compresslemekteustadegilimacikcasinefretdeediomniyeyapmakzorundayiz[i]]=i;
}
n=segment.size();
vector<int> arr(n+1,0);
vector<int> barr(n+1,0);
Solution soln;
sort(segment.begin(), segment.end(), [&](pair<int,int> a, pair<int,int> b){
return (a.first+a.second)<(b.first+b.second);
});
for (int i = 1; i <= n; i++){
soln.push(segment[i-1].first,segment[i-1].second);
arr[i]=soln.query();
}
for (int i = 1; i <= n; i++){
barr[n-i+1]=soln.query();
soln.erase(segment[i-1].first,segment[i-1].second);
}
if (k==1) ans+=arr[n];
else {
int crr = arr[0]+barr[n];
for (int i = 0; i <= n; i++){
crr=min(arr[i]+barr[n-i],crr);
}
ans+=crr;
}
cout<<ans<<endl;
}
}
