// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM2
#define LMOD 1000000006LL
#define fi first
#define se second
typedef long double ld;
const ll MAX = 3000100;
const ll INF = 1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class MedianFind{
private:
multiset<ll> low, hi;
ll lowsum = 0, hisum = 0;
ll cnt = 0;
public:
void balance(){
while(low.size() < hi.size()){
ll v = *hi.begin();
hi.erase(hi.begin());
hisum -= v;
low.insert(v);
lowsum += v;
}
while(low.size() > hi.size() + 1){
ll v = *low.rbegin();
low.erase(low.find(v));
lowsum -= v;
hi.insert(v);
hisum += v;
}
}
void insert(ll val){
cnt++;
if(low.empty()){
low.insert(val);
lowsum += val;
return;
}
else{
if(val > *low.rbegin()){
hi.insert(val);
hisum += val;
}
else{
low.insert(val);
lowsum += val;
}
balance();
return;
}
}
void remove(ll val){
--cnt;
if(low.find(val) != low.end()){
low.erase(low.find(val));
lowsum -= val;
}
else{
hi.erase(hi.find(val));
hisum -= val;
}
balance();
}
ll findMedian(){
if(low.empty()) return -1;
return *low.rbegin();
}
ll findval(){
if(cnt == 0) return 0ll;
ll med = findMedian();
return (low.size()*med - lowsum + hisum - (med*hi.size()));
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll k, n;
cin >> k >> n;
ll inval = 0;
vector<pair<ll, ll>> ed;
for(ll i = 0; i < n; i++){
ll s, t;
char p, q;
cin >> p >> s >> q >> t;
if(p == q) inval += abs(s - t);
else{
ed.push_back({s, t});
}
}
if(k == 1){
vector<ll> v;
for(auto& x: ed){
v.push_back(x.fi);
v.push_back(x.se);
}
sort(all(v));
// for(auto& x: v) cerr << x << ' ';
// cerr << '\n';
ll k = v.size();
ll med = v[k/2];
for(auto& x: v) inval += abs(med - x);
inval += ed.size();
cout << inval << '\n';
exit(0);
}
auto cmp = [](pair<ll, ll> a, pair<ll, ll> b){
return a.fi + a.se < b.fi + b.se;
};
sort(all(ed), cmp);
MedianFind med1, med2;
n = ed.size();
for(ll i = 0; i < n; i++){
med2.insert(ed[i].fi);
med2.insert(ed[i].se);
}
ll minval = med2.findval();
for(ll i = 0; i < n; i++){
med1.insert(ed[i].fi);
med1.insert(ed[i].se);
med2.remove(ed[i].fi);
med2.remove(ed[i].se);
minval = min(minval, med1.findval() + med2.findval());
}
cout << minval + inval + ed.size();
return 0;
}
