#include<bits/stdc++.h>
#define debug(v) //cerr << #v << ": " << v << '\n';
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int k, n;
ll ans;
vector<pii> inter;
bool cmp(pii a, pii b){
return a.first+a.second < b.first+b.second;
}
struct two_set{
multiset<int> s1, s2;
//s1-> smaller or equal than mid
//s2 -> greater or equal than mid;
//s1.size() >= s2.size();
ll sum1, sum2;
ll median(){
if(s1.empty()){
// cerr << "empty set\n";
return 0;
}
return *s1.rbegin();
}
void add(int v){
if(s1.empty()){
s1.insert(v);
sum1 += v;
return;
}
if(s1.size() == s2.size()){
if(v <= *s2.begin()){
sum1 += v;
s1.insert(v);
}
else{
sum2 += v;
s2.insert(v);
sum1 += *s2.begin();
s1.insert( *s2.begin() );
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
}
else{
if(v <= *s1.rbegin()){
sum2 += *(--s1.end());
s2.insert( *(--s1.end()) );
sum1 -= *(--s1.end());
s1.erase( --s1.end() );
sum1 += v;
s1.insert(v);
}
else{
sum2 += v;
s2.insert(v);
}
}
}
void remove(int v){
if(s1.size() == s2.size()){
if(v < *s2.begin()){
sum1 -= v;
s1.erase(s1.find(v));
sum1 += *s2.begin();
s1.insert(*s2.begin());
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
else{
sum2 -= v;
s2.erase(s2.find(v));
}
}
else{
if(v <= *s1.rbegin()){
sum1 -= v;
s1.erase(s1.find(v));
}
else{
sum2 -= v;
s2.erase(s2.find(v));
sum2 += *(--s1.end()) ;
s2.insert( *(--s1.end()) );
sum1 -= *(--s1.end()) ;
s1.erase( --s1.end() );
}
}
}
ll dist(){
return median()*s1.size()-sum1 + sum2 - median()*s2.size();
}
};
two_set esq, dir;
signed main(){
cin.tie(0)->sync_with_stdio(0);
int k, n;
cin >> k >> n;
for(int i = 1; i <= n; i++){
char za, zb; int a, b;
cin >> za >> a >> zb >> b;
if(a>b) swap(a, b);
if(za==zb){
ans += b-a;
}
else{
ans++;
inter.push_back({a, b});
}
}
debug(ans)
sort(inter.begin(), inter.end(), cmp);
for(auto[L, R] : inter){
dir.add(L);
dir.add(R);
debug(L);
debug(R);
debug(dir.median());
debug(dir.dist());
}
debug(dir.median());
ll best = ans+dir.dist();
if(k == 1 || inter.empty()){
cout << best << '\n';
return 0;
}
for(auto[L, R] : inter){
dir.remove(L);
dir.remove(R);
esq.add(L);
esq.add(R);
debug(dir.median());
debug(dir.dist());
debug(esq.median());
debug(esq.dist());
debug(' ');
best = min(best, dir.dist()+esq.dist());
}
debug(best)
cout << ans+best << '\n';
}
