#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, M = 2e5 + 5;
int a[M], m, cp[M], to_rem[N];
bool ok[N];
ll bit[2][M];
pii P[N], V[M];
int pos(int x){ return upper_bound(cp, cp+m, x) - cp;}
ll upd(int x, int i, ll val){ for(; i<M; i+=i&-i) bit[x][i] += val;}
ll qry(int x, int i){ ll res = 0; for(; i; i-=i&-i) res += bit[x][i]; return res;}
int _find(int k){
int sum = 0, i = 0;
for(int j = 18; j>=0; --j){
if(i+(1<<j) < M && sum + bit[0][i+(1<<j)] < k) sum += bit[0][i+=(1<<j)];
}
return i + 1;
}
signed main(){
int k, n; m = 0; scanf("%d %d", &k, &n);
if(k == 1){
ll tot = 0; char c[2];
for(int i = 0, p[2]; i<n; ++i){
scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
if(c[0] == c[1]) tot += p[1] - p[0];
else{ a[m++] = p[0]; a[m++] = p[1];}
}
sort(a, a+m);
for(int i = 0; i<m; ++i) tot += abs(a[i] - a[m/2 - 1]);
printf("%lld", tot + m/2);
}else{
ll tot = 0, sum[2] = {0, 0};
for(int i = 0, p[2]; i<n; ++i){
char c[2];
scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
if(c[0] == c[1]) tot += p[1] - p[0];
else{
cp[m] = p[0]; V[m++] = mp(p[0], i);
cp[m] = p[1]; V[m++] = mp(p[1], i);
P[i] = mp(p[0], p[1]);
ok[i] = true;
++tot;
}
}
int sz = m, cnt = 0;
sort(cp, cp+m); m = unique(cp, cp+m) - cp;
sort(V, V+sz);
for(int i = 0; i<n; ++i){
if(ok[i]){
int idx[2] = {pos(P[i].F), pos(P[i].S)};
upd(0, idx[0], +1); upd(0, idx[1], +1);
upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
cnt += 2;
}
}
int I = _find((cnt+1)/2);
ll fp = qry(0, I) * cp[I-1] - qry(1, I);
ll sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
ll md = fp + sp, not_md = 0, mn = 2e18;
set<int> s;
for(int i = 0, j; i<sz; ){
int t = 0;
for(j = i; V[j].F == V[i].F; ++j){
if(s.find(V[j].S) == s.end()){
s.insert(V[j].S);
int idx[2] = {pos(P[V[j].S].F), pos(P[V[j].S].S)};
upd(0, idx[0], -1); upd(0, idx[1], -1);
upd(1, idx[0], -P[i].F); upd(1, idx[1], -P[i].S);
cnt -= 2;
not_md += P[V[j].S].S - P[V[j].S].F;
}else{
to_rem[t++] = V[j].S;
}
}
//
I = _find((cnt+1)/2);
fp = qry(0, I) * cp[I-1] - qry(1, I);
sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
md = fp + sp;
mn = min(mn, md + not_md);
//
for(int w = 0; w<t; ++w){
s.erase(to_rem[w]);
int idx[2] = {pos(P[to_rem[j]].F), pos(P[to_rem[j]].S)};
upd(0, idx[0], +1); upd(0, idx[1], +1);
upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
cnt += 2;
not_md -= P[to_rem[w]].S - P[to_rem[w]].F;
}
//
i = j;
}
printf("%lld", tot + cnt * mn);
}
}
