#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long long,long long>,null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define all(x) (x).begin(), (x).end()
#define king ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(0)
int n, k, maxn;
oset st;
vector<ll> tr; // sums
vector<int> trCnt; // counts
// Fenwick for sums
ll queSum(int i){
ll sm=0;
for(; i>=1; i-=i&-i) sm += tr[i];
return sm;
}
void upSum(int i,ll x){
for(; i<=maxn; i+=i&-i) tr[i] += x;
}
// Fenwick for counts
int queCnt(int i){
int sm=0;
for(; i>=1; i-=i&-i) sm += trCnt[i];
return sm;
}
void upCnt(int i,int x){
for(; i<=maxn; i+=i&-i) trCnt[i] += x;
}
map<ll,int> pos;
ll totalSumAll = 0;
ll cal(bool useLeftMedian){
if(st.size() == 0) return 0;
// choose median index (order in st)
size_t sz = st.size();
size_t posIndex;
if(useLeftMedian){
// left median for even size
posIndex = sz/2 - 1;
} else {
// right median for even size
posIndex = sz/2;
}
// get iterator to that ordered element
auto it = st.find_by_order(posIndex);
ll x = it->first;
// compressed position of value x
int p = pos[x];
// counts and sums strictly less than value x
int countLess = queCnt(p-1);
ll sumLess = queSum(p-1);
// total count left of chosen pair in st (including equal-values that are before this pair)
int countLeft = (int)posIndex;
// number of equal-value elements that are before the chosen pair
int equalBefore = countLeft - countLess;
// low should include sumLess plus equalBefore * x
ll low = sumLess + (ll)equalBefore * x;
// counts and sums strictly greater than value x
int countGreater = queCnt(maxn) - queCnt(p);
ll sumGreater = queSum(maxn) - queSum(p);
// number of elements strictly after chosen pair in st
int countRight = (int)sz - (int)posIndex - 1;
// sum of elements after chosen pair equals sumGreater (elements equal to x after the chosen pair contribute 0 to distance)
ll hi = sumGreater;
ll leftCost = x * (ll)countLeft - low;
ll rightCost = hi - x * (ll)countRight;
return leftCost + rightCost;
}
vector<tuple<ll,ll,ll>> vec;
vector<ll> pf, suf;
int main(){
king;
cin >> k >> n;
maxn = 2 * n + 5;
tr.assign(maxn + 5, 0);
trCnt.assign(maxn + 5, 0);
vector<ll> com;
vector<ll> k1;
ll ans = 0;
for(int i = 1; i <= n; ++i){
char q,w;
int x,y;
cin >> q >> x >> w >> y;
if(q == w){
ans += llabs((ll)x - (ll)y);
} else {
ans++;
vec.push_back({(x + y) / 2, x, y});
if(k == 1){
k1.push_back(x);
k1.push_back(y);
}
}
com.push_back(x);
com.push_back(y);
}
if(k == 1){
if(k1.empty()){
cout << ans << '\n';
return 0;
}
sort(all(k1));
size_t m = k1.size();
size_t mid = m/2;
// choose left median (either left or right median gives same minimal sum for even count)
if(mid == 0){
cout << ans << '\n';
return 0;
}
mid = mid - 1;
ll x = k1[mid];
ll low = 0, hi = 0;
for(size_t i = 0; i < mid; ++i) low += k1[i];
for(size_t i = mid+1; i < m; ++i) hi += k1[i];
cout << ans + (x * (ll)mid - low) + (hi - x * (ll)(mid + 1)) << '\n';
return 0;
}
sort(all(com));
com.erase(unique(all(com)), com.end());
for(size_t i = 0; i < com.size(); ++i) pos[com[i]] = (int)(i + 1);
if(vec.empty()){
cout << ans << '\n';
return 0;
}
pf.assign(vec.size(), 0);
suf.assign(vec.size(), 0);
// prefix pass (use left median)
size_t cnt = 0;
for(size_t i = 0; i < vec.size(); ++i){
auto [s,x,y] = vec[i];
st.insert({x, cnt++});
st.insert({y, cnt++});
upSum(pos[x], x);
upSum(pos[y], y);
upCnt(pos[x], 1);
upCnt(pos[y], 1);
pf[i] = cal(true); // left median
}
// suffix pass: clear and rebuild from reversed vec (use right median)
st.clear();
fill(tr.begin(), tr.end(), 0);
fill(trCnt.begin(), trCnt.end(), 0);
cnt = 0;
reverse(all(vec));
for(size_t i = 0; i < vec.size(); ++i){
auto [s,x,y] = vec[i];
st.insert({x, cnt++});
st.insert({y, cnt++});
upSum(pos[x], x);
upSum(pos[y], y);
upCnt(pos[x], 1);
upCnt(pos[y], 1);
suf[(vec.size()-1) - i] = cal(false); // right median
}
ll mn = (ll)4e18;
if(vec.size() == 1){
mn = min(pf[0], suf[0]);
} else {
for(size_t i = 0; i + 1 < vec.size(); ++i){
mn = min(mn, pf[i] + suf[i+1]);
}
}
cout << mn + ans << '\n';
return 0;
}
