#include<bits/stdc++.h> #define ll long long using namespace std; bool cmp(array<int,2> x,array<int,2> y) { return x[0] + x[1] < y[0] + y[1]; } const int maxN = (int)1e5 + 2; ll sum_left[maxN],sum_right[maxN]; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int k , n; cin >> k >> n; ll ans = 0; if(k == 1) { vector<int> x_coords; x_coords.clear(); while(n--) { char c1,c2; int x1,x2; cin >> c1 >> x1 >> c2 >> x2; if(c1 == c2) ans += abs(x2 - x1); else ++ans,x_coords.push_back(x1),x_coords.push_back(x2); } sort(x_coords.begin(),x_coords.end()); int med_idx = x_coords.size() / 2; for(int x : x_coords) ans += abs(x - x_coords[med_idx]); } else { vector<array<int,2>> coords; coords.clear(); while(n--) { int x1,x2; char c1,c2; cin >> c1 >> x1 >> c2 >> x2; if(c1 == c2) ans += abs(x2 - x1); else ++ans,coords.push_back({x1,x2}); } sort(coords.begin(),coords.end(),cmp); n = coords.size(); multiset<int> ms1,ms2; ms1.clear(),ms2.clear(); ll l_sum = 0,r_sum = 0; for(int i=0;i<n;++i) { int x1 = coords[i][0],x2 = coords[i][1]; if(x1 > x2) swap(x1,x2); ms1.insert(x1),ms2.insert(x2); l_sum += x1,r_sum += x2; if(*ms2.begin() < *ms1.rbegin()) { int v; v = *ms2.begin(); ms2.erase(ms2.begin()); r_sum -= v; ms1.insert(v); l_sum += v; v = *ms1.rbegin(); ms1.erase(ms1.find(v)); l_sum -= v; ms2.insert(v); r_sum += v; } ll median = *ms1.rbegin(); sum_left[i] = median * ms1.size() - l_sum + r_sum - median * ms2.size(); } ms1.clear(),ms2.clear(); l_sum = 0,r_sum = 0; for(int i=n-1;i>=0;--i) { int x1 = coords[i][0]; int x2 = coords[i][1]; if(x1 > x2) swap(x1,x2); ms1.insert(x1),ms2.insert(x2); l_sum += x1,r_sum += x2; if(*ms1.rbegin() > *ms2.begin()) { int v; v = *ms2.begin(); ms2.erase(ms2.begin()); r_sum -= v; ms1.insert(v); l_sum += v; v = *ms1.rbegin(); ms1.erase(ms1.find(v)); l_sum -= v; ms2.insert(v); r_sum += v; } ll median = *ms1.rbegin(); sum_right[i] = median * ms1.size() - l_sum + r_sum - median * ms2.size(); } ll min_cost = LONG_LONG_MAX; for(int i=0;i<n-1;++i) min_cost = min(min_cost,sum_left[i] + sum_right[i+1]); ans += min({min_cost,sum_left[n-1],sum_right[0]}); } cout << ans; return 0; }