#include "bits/stdc++.h"
using namespace std;
#define int long long
#define left oawenopigeawg
#define right awhopegiheoag
const int maxn = 2e5 + 5;
const int inf = 1e18;
int n, k;
struct interval {
int x, op, id;
bool operator<(const interval &o) {
return x < o.x;
}
};
pair<int, int> a[maxn];
namespace sub12 {
void solve() {
int ans = inf;
int sum = 0;
vector<interval> sweep;
int sz = 0;
for(int i = 1; i <= n; ++i) {
int l, r;
char x, y;
cin >> x >> l >> y >> r;
if(l > r) swap(l, r);
if(x == y) {
sum += (r - l);
}
else {
++sz;
sweep.push_back({l, 1, sz});
sweep.push_back({r, -1, sz});
a[sz] = {l, r};
}
}
n = sz;
sort(sweep.begin(), sweep.end());
set<int> s;
int others = 0;
int nxt = 0, cur_sum = 0;
for(int i = 1; i <= n; ++i) {
nxt += (a[i].first + a[i].second);
}
ans = nxt;
int pref = 0, suf = n;
for(int i = 0; i < (int)sweep.size(); ++i) {
int cur = 0;
while(i + cur < (int)sweep.size() and sweep[i].x == sweep[i + cur].x) {
int op = sweep[i + cur].op, id = sweep[i + cur].id;
if(op == 1) {
s.insert(id);
cur_sum += (a[id].second - a[id].first);
nxt -= (a[id].first + a[id].second);
--suf;
}
else {
others += (a[id].first + a[id].second);
s.erase(id);
cur_sum -= (a[id].second - a[id].first);
++pref;
}
int x = sweep[i].x;
int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
// cerr << i + cur << " " << s.size() << " " << pref << " " << suf << " " << others << " " << nxt << " " << res << '\n';
++cur;
}
int x = sweep[i].x;
int res = cur_sum + (2 * pref * x - others) + (nxt - 2 * x * suf);
ans = min(ans, res);
i = i + cur - 1;
}
cout << ans + sum + sz;
}
}
namespace sub34 {
multiset<int> left, right;
int left_sum, right_sum;
void adjust() {
while((int)left.size() and right.size()) {
if(*(--left.end()) <= *(right.begin())) {
break;
}
int it = *(--left.end());
left_sum -= it;
left.erase(left.find(it));
right.insert(it);
right_sum += it;
}
while((int)left.size() - (int)right.size() > 1) {
int it = *(--left.end());
left.erase(left.find(it));
left_sum -= it;
right_sum += it;
right.insert(it);
}
while((int)right.size() - (int)left.size() > 0) {
int it = *(right.begin());
right.erase(right.find(it));
right_sum -= it;
left_sum += it;
left.insert(it);
}
}
void erase(int x) {
if(left.find(x) != left.end()) {
left.erase(left.find(x));
left_sum -= x;
}
else if(right.find(x) != right.end()) {
right.erase(right.find(x));
right_sum -= x;
}
adjust();
}
void solve() {
int ans = inf;
vector<int> vec;
int sum = 0;
vector<interval> sweep;
int sz = 0;
for(int i = 1; i <= n; ++i) {
int l, r;
char x, y;
cin >> x >> l >> y >> r;
if(l > r) swap(l, r);
if(x == y) {
sum += (r - l);
}
else {
++sz;
sweep.push_back({l, 1, sz});
sweep.push_back({r, -1, sz});
vec.push_back(l);
vec.push_back(r);
a[sz] = {l, r};
}
}
n = sz;
sort(sweep.begin(), sweep.end());
sort(vec.begin(), vec.end());
sort(a + 1, a + n + 1, [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
return x.first + x.second < y.first + y.second;
});
vector<int> pref(sz + 1), suf(sz + 1);
for(int i = 1; i <= n; ++i) {
left.insert(a[i].first);
left.insert(a[i].second);
left_sum += a[i].first;
left_sum += a[i].second;
adjust();
pref[i] = inf;
if(left.size()) {
int cur_med = *(--left.end());
pref[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
// cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << pref[i] << '\n';
// for(auto i:right) cerr << i << " ";
// cerr << '\n';
}
}
left.clear();
right.clear();
left_sum = right_sum = 0;
cerr << '\n';
for(int i = n; i; --i) {
left.insert(a[i].first);
left.insert(a[i].second);
left_sum += a[i].first;
left_sum += a[i].second;
adjust();
if(left.size()) {
int cur_med = *(--left.end());
suf[i] = (cur_med * (left.size()) - left_sum) + (right_sum - cur_med * (right.size()));
// cerr << i << " " << left_sum << " " << right_sum << " " << cur_med << " " << suf[i] << '\n';
}
}
for(int i = 0; i <= n; ++i) {
ans = min(ans, pref[i] + suf[i + 1]);
// cerr << i << " " << pref[i] << " " << suf[i + 1] << '\n';
}
cout << ans + sz + sum;
}
}
void solve() {
cin >> k >> n;
if(k == 1) {
sub12::solve();
return;
}
if(k == 2) {
sub34::solve();
return;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
