#include <bits/stdc++.h>
#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 10007
#define left lleft
#define right rright
#define INF 2000000000
#define LINF 1000000000000000000LL
#define next nnext
using namespace std;
int N,K,rear,nn;
int tx,ty,tx2,ty2,btx2,bty2,t1,t2;
lld memo,ans,sum,bsum;
lld cnt1,cnt2,cnt3,cnt4;
vector<lld> X;
struct IN{
int x,y;
}in[100002];
struct data{
int x,num;
}a[100002],b[100002];
vector<int> Value;
struct SEG{
lld sum,cnt;
}seg[300002];
void process1(){
for(int i=1; i<=N; i++){
sum += (a[i].x+b[i].x-X[0]-X[0]);
if(a[i].x > X[0]) cnt2++;
}
ans = min(ans,sum);
while(1){
if(tx == N || a[tx+1].x > X[0]) break;
tx++;
}
for(int i=1; i<X.size(); i++){
sum += (2*cnt1*(X[i]-X[i-1])); sum -= (2*cnt2*(X[i]-X[i-1]));
while(1){
if(tx == N || a[tx+1].x > X[i]) break;
tx++;
cnt2--;
}
while(1){
if(ty == N || b[ty+1].x > X[i-1]) break;
ty++;
cnt1++; sum += (X[i]-X[i-1])*2;
}
ans = min(ans,sum);
}
}
int change(int x){
return lower_bound(Value.begin(),Value.end(),x)-Value.begin()+1;
}
SEG getseg(int node,int l,int r,int s,int e){
if(r < s || e < l || s > e) return {0,0};
if(s <= l && r <= e) return seg[node];
int mid = (l+r)/2;
SEG tmp1,tmp2;
tmp1 = getseg(node*2,l,mid,s,e);
tmp2 = getseg(node*2+1,mid+1,r,s,e);
tmp1.sum += tmp2.sum; tmp1.cnt += tmp2.cnt;
return tmp1;
}
SEG get2(lld s,lld e){
int it1,it2;
it1 = change(s); it2 = change(e+1);
if(it2 == 1) return {0,0};
it2--;
return getseg(1,1,nn,it1,it2);
}
lld get(){
int mid = X[t1]+X[t2];
SEG tmp1,tmp2;
tmp1 = get2((X[t1]+1)*2,mid);
tmp2 = get2(mid+1,((X[t2]-1)*2));
lld tsum = 0;
tsum += (tmp1.sum-tmp1.cnt*2*X[t1]);
tsum += (tmp2.cnt*2*X[t2]-tmp2.sum);
return tsum;
}
void update(int x,int add){
int value = Value[x-1];
x += (nn-1);
while(x){
seg[x].sum += value*add;
seg[x].cnt += add;
x /= 2;
}
}
void addt2(){
t2++;
sum -= (2*cnt2*(X[t2]-X[t2-1]));
btx2 = tx2; bty2 = ty2;
while(1){
if(tx2 == N || a[tx2+1].x > X[t2]) break;
tx2++;
cnt2--;
}
while(1){
if(ty2 == N || b[ty2+1].x > X[t2-1]) break;
ty2++;
if(in[b[ty2].num].x <= X[t1]) continue;
//segupdate
update(change(in[b[ty2].num].x+in[b[ty2].num].y),1);
int x,y;
x = in[b[ty2].num].x; y = in[b[ty2].num].y;
sum -= (y-x);
}
}
void undo(){
for(int i=bty2+1; i<=ty2; i++){
if(in[b[i].num].x <= X[t1]) continue;
//segupdate
update(change(in[b[i].num].x+in[b[i].num].y),-1);
int x,y;
x = in[b[i].num].x; y = in[b[i].num].y;
sum += (y-x);
}
cnt2 += (tx2-btx2);
tx2 = btx2; ty2 = bty2;
sum += (2*cnt2*(X[t2]-X[t2-1]));
t2--;
}
void process2(){
for(int i=1; i<=N; i++){
sum += (a[i].x+b[i].x-X[0]-X[0]);
if(a[i].x > X[0]) cnt2++;
}
if(X.size() <= 1){
ans = sum;
return;
}
while(1){
if(tx == N || a[tx+1].x > X[0]) break;
tx++; tx2++;
}
while(1){
if(t2 == X.size()-1) break;
bsum = sum+get();
addt2();
if(sum+get() > bsum){
undo();
break;
}
}
ans = min(ans,sum+get());
while(t1+1 < X.size()-1){
if(t2 == t1+1) addt2();
//t1++
t1++;
sum += (2*cnt1*(X[t1]-X[t1-1]));
while(1){
if(tx == N || a[tx+1].x > X[t1]) break;
tx++;
if(in[a[tx].num].y >= X[t2]) continue;
else{
//seg update
update(change(in[a[tx].num].x+in[a[tx].num].y),-1);
int x,y;
x = in[a[tx].num].x; y = in[a[tx].num].y;
sum += (y-x);
}
}
while(1){
if(ty == N || b[ty+1].x > X[t1-1]) break;
ty++;
cnt1++;
sum += (2*(X[t1]-X[t1-1]));
}
while(1){
if(t2 == X.size()-1) break;
bsum = sum+get();
addt2();
if(sum+get() > bsum){
undo();
break;
}
}
ans = min(ans,sum+get());
}
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d %d",&K,&N);
for(int i=1; i<=N; i++){
int x,y;
char op1,op2;
scanf("\n%c %d %c %d",&op1,&x,&op2,&y);
if(x > y) swap(x,y);
if(op1 == op2) memo += (y-x);
else{
rear++;
a[rear].x = x; a[rear].num = rear;
b[rear].x = y; b[rear].num = rear;
X.pb(x); X.pb(y);
memo++;
in[rear].x = x; in[rear].y = y;
Value.pb(x+y);
}
}
N = rear; ans = LINF;
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
sort(Value.begin(),Value.end());
Value.erase(unique(Value.begin(),Value.end()),Value.end());
for(nn=1; nn<Value.size(); nn*=2);
sort(a+1,a+N+1,[&](data &x,data &y){
return x.x < y.x;
});
sort(b+1,b+N+1,[&](data &x,data &y){
return x.x < y.x;
});
if(K == 1) process1();
else process2();
ans += memo;
printf("%lld\n",ans);
return 0;
}
