#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, p[N];
vector<ll> a;
vector<pii> inf;
map<int, int> in;
bool cmp(pii a, pii b) {
return (a.f+a.s)<(b.f+b.s);
}
ll s[4];
void fix(int in, multiset<int> &a, multiset<int> &b) {
int tot=a.size()+b.size();
while(a.size()>(tot+1)/2) {
int val=*a.rbegin();
a.erase(a.find(val));
s[in]-=val;
b.insert(val);
s[in+1]+=val;
}
while(b.size()>tot/2) {
int val=*b.begin();
b.erase(b.find(val));
s[in+1]-=val;
a.insert(val);
s[in]+=val;
}
}
ll calc() {
return s[1]-s[0]+s[3]-s[2];
}
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;
}
multiset<int> l, r, le, ri;
sort(inf.begin(), inf.end(), cmp);
FOR(i, 0, inf.size()) {
le.insert(inf[i].f);
le.insert(inf[i].s);
s[2]+=inf[i].f+inf[i].s;
}
while(le.size()>(le.size()+ri.size()+1)/2) {
int val=*le.rbegin();
le.erase(le.find(val));
ri.insert(val);
s[2]-=val; s[3]+=val;
}
ll ret=calc()+ans;
if(k==1) {
cout << ret;
return 0;
}
FOR(i, 0, inf.size()) {
int val=inf[i].f;
if(l.empty()) l.insert(val), s[0]+=val;
else {
int md=*l.rbegin();
if(val>=md) r.insert(val), s[1]+=val;
else l.insert(val), s[0]+=val;
}
if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
else ri.erase(ri.find(val)), s[3]-=val;
val=inf[i].s;
if(l.empty()) l.insert(val), s[0]+=val;
else {
int md=*l.rbegin();
if(val>=md) r.insert(val), s[1]+=val;
else l.insert(val), s[0]+=val;
}
if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
else ri.erase(ri.find(val)), s[3]-=val;
fix(0, l, r);
fix(2, le, ri);
ret=min(ret, ans+calc());
}
cout << ret;
}
