#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N=1e5+10;
int k, n;
ll ans, suff[N];
vector<int> a;
vector<pii> inf;
bool cmp(pii a, pii b) {
return (a.f+a.s)<(b.f+b.s);
}
ll s[4];
void fix(priority_queue<int> &l, priority_queue<int, vector<int>, greater<int>> &r) {
while(l.size()>r.size()) {
int val=l.top(); l.pop();
r.push(val);
s[0]-=val; s[1]+=val;
}
while(r.size()>l.size()) {
int val=r.top(); r.pop();
l.push(val);
s[0]+=val; s[1]-=val;
}
}
ll calc() {
return s[1]-s[0];
}
int main() {
FAST_IO;
cin >> k >> n;
FOR(i, 0, n) {
char c1, c2; int x1, x2;
cin >> c1 >> x1 >> c2 >> x2;
if(c1==c2) {
ans+=abs(x1-x2);
}
else {
inf.pb({x1,x2});
a.pb(x1);
a.pb(x2);
}
}
sort(a.begin(), a.end());
n=a.size();
ans+=n/2;
if(n==0) {
cout << ans;
return 0;
}
sort(inf.begin(), inf.end(), cmp);
priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;
for(int i=(int)inf.size()-1; i>=0; i--) {
int val=inf[i].f;
if(l.empty()) l.push(val), s[0]+=val;
else {
int md=l.top();
if(val>=md) r.push(val), s[1]+=val;
else l.push(val), s[0]+=val;
}
val=inf[i].s;
int md=l.top();
if(val>=md) r.push(val), s[1]+=val;
else l.push(val), s[0]+=val;
fix(l, r);
suff[i]=calc();
}
if(k==1) {
cout << suff[0]+ans;
return 0;
}
while(!l.empty()) l.pop();
while(!r.empty()) r.pop();
s[0]=s[1]=0;
ll ret=suff[0]+ans;
FOR(i, 0, inf.size()) {
int val=inf[i].f;
if(l.empty()) l.push(val), s[0]+=val;
else {
int md=l.top();
if(val>=md) r.push(val), s[1]+=val;
else l.push(val), s[0]+=val;
}
val=inf[i].s;
int md=l.top();
if(val>=md) r.push(val), s[1]+=val;
else l.push(val), s[0]+=val;
fix(l, r);
// cout << i << ": " << calc() << " " << suff[i+1] << endl;
ret=min(ret, calc()+ans+suff[i+1]);
}
cout << ret;
}
