//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 500005
using namespace std;
ll k, n;
ll ans_goc = 0;
pii a[N];
vector<ll> nenSo;
void sub1() {
ll ans = inf;
sort(a + 1, a + 1 + n);
ll sum = 0;
ll cur_p = -1;
ll cnt_r = n, cnt_l = 0;
for (int i = 1; i <= n; i ++) {
ll l = a[i].fi, r = a[i].se;
//cout << i << " " << l << " " << r << " " << sum << endl;
sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
}
//cout << "sum bd: " << sum << endl;
ans = min(ans, sum);
ll id = 1;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 1; i < nenSo.size(); i ++) {
ll nxt_p = nenSo[i];
while (pq.size() && pq.top().fi < nxt_p) {
cnt_l ++ ;
pq.pop();
}
sum -= cnt_r * (nxt_p - cur_p) * 2;
sum += cnt_l * (nxt_p - cur_p) * 2;
while (id <= n && a[id].fi <= nxt_p) {
cnt_r -- ;
pq.push({a[id].se, id});
id ++ ;
}
//cout << i << " " << nxt_p << " " << sum << endl;
ans = min(ans, sum);
cur_p = nxt_p;
}
cout << ans + ans_goc;
}
ll pf[2001][1001], sf[2001][1001], b[N];
bool cmp(pii a, pii b) {
return a.fi + a.se < b.fi + b.se;
}
void sub2() {
if (n == 0) {
cout << ans_goc;
return;
}
if (n == 1) {
cout << a[1].se - a[1].fi + 1;
return;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i ++) {
b[i] = a[i].fi + a[i].se;
}
for (int i = 1; i < nenSo.size(); i ++) {
ll sum = 0;
ll cur_p = nenSo[i];
for (int j = 1; j <= n; j ++){
ll l = a[j].fi, r = a[j].se;
if (l <= cur_p && cur_p <= r) {
sum += (r - l) + 1;
pf[i][j] = sum;
continue;
}
sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
pf[i][j] = sum;
}
sum = 0;
for (int j = n; j >= 1; j --){
ll l = a[j].fi, r = a[j].se;
if (l <= cur_p && cur_p <= r) {
sum += (r - l) + 1;
sf[i][j] = sum;
continue;
}
sum += (r - l) + min(abs(r - cur_p), abs(l - cur_p)) * 2 + 1;
sf[i][j] = sum;
}
}
ll ans = inf;
for (int i = 1; i < nenSo.size(); i ++) {
for (int j = i + 1; j < nenSo.size(); j ++) {
ll l = nenSo[i], r = nenSo[j];
auto it = upper_bound(b + 1, b + 1 + n, l + r) - b - 1;
ans = min(ans, pf[i][it] + sf[j][it + 1]);
}
}
cout << ans + ans_goc;
}
ll prefix[N], suffix[N], pre_me[N], suf_me[N], sum_mx, sum_mn;
priority_queue<ll, vector<ll>, greater<ll>> min_heap;
priority_queue<ll> max_heap;
void add(ll num) {
if (max_heap.size() == 0 || num <= max_heap.top()) {
max_heap.push(num);
sum_mx += num;
}
else {
min_heap.push(num);
sum_mn += num;
}
if (max_heap.size() > min_heap.size() + 1) {
min_heap.push(max_heap.top());
sum_mn += max_heap.top();
sum_mx -= max_heap.top();
max_heap.pop();
}
else if (min_heap.size() > max_heap.size()) {
max_heap.push(min_heap.top());
sum_mx += min_heap.top();
sum_mn -= min_heap.top();
min_heap.pop();
}
}
ll find_med() {
if (max_heap.size() >= min_heap.size()) {
return max_heap.top();
}
if (min_heap.size() > max_heap.size()) {
return min_heap.top();
}
return max_heap.top();
}
void sub3() {
if (n == 0) {
cout << ans_goc;
return;
}
if (n == 1) {
cout << a[1].se - a[1].fi + 1;
return;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i ++) {
b[i] = a[i].fi + a[i].se;
}
for (int i = 1; i <= n; i ++) {
ll ps = a[i].fi, pe = a[i].se;
add(ps);
add(pe);
pre_me[i] = find_med();
ll med = pre_me[i];
prefix[i] = med * max_heap.size() - sum_mx + sum_mn - med * min_heap.size();
}
while (max_heap.size()) max_heap.pop();
while (min_heap.size()) min_heap.pop();
sum_mn = sum_mx = 0;
ll ans = inf;
for (int i = n; i >= 1; i --) {
ll ps = a[i].fi, pe = a[i].se;
add(ps);
add(pe);
suf_me[i] = find_med();
ll med = suf_me[i];
suffix[i] = med * max_heap.size() - sum_mx + sum_mn - med * min_heap.size();
}
for (int i = 1; i <= n - 1; i ++) {
ans = min(ans, prefix[i] + suffix[i + 1]);
}
cout << ans + ans_goc + n;
}
signed main(void) {
faster;
ll curid = 0;
cin >> k >> n;
for (int i = 1; i <= n; i ++) {
char bs1, bs2; ll p1, p2;
cin >> bs1 >> p1 >> bs2 >> p2;
if (bs1 == bs2) {
ans_goc += abs(p1 - p2);
continue;
}
curid ++ ;
if (p1 > p2) swap(p1, p2);
a[curid] = {p1, p2};
nenSo.push_back(p1);
nenSo.push_back(p2);
}
n = curid;
nenSo.push_back(-inf);
sort(nenSo.begin(), nenSo.end());
nenSo.resize(unique(nenSo.begin(), nenSo.end()) - nenSo.begin());
if (k == 1) {
sub1();
}
else if (k == 2) {
sub3();
}
return 0;
}
