#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second
#define ff first
#define ss second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
typedef complex<double> ftype;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;
template <typename T1, typename T2>
istream& operator>>(istream& is, pair <T1, T2>& a){
is >> a.ff >> a.ss;
return is;
}
template<typename T>
istream &operator>>(istream &in, vector<T> &list){
for (auto &x: list)
in >> x;
return in;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair <T1, T2> a){
os << a.ff << " " << a.ss << " ";
return os;
}
template<typename T>
ostream &operator<<(ostream &out, const vector<T> &list) {
for (auto x : list)
out << x << " ";
return out;
}
mt19937 rnd(31);
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
//#pragma GCC optimize(3)
/*#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")*/
//-------------------------------------------
const int MAXN = 2e5 + 10;
pt poses[MAXN];
vector<int> start[MAXN], stop[MAXN];
ll solve1(int n){
if (n == 0)
return 0;
sort(poses, poses + n, [&](pt a, pt b){return a.y < b.y;});
ll ans = 1e18;
vector<int> xs;
for (int i = 0; i < n; i++){
xs.push_back(poses[i].x);
xs.push_back(poses[i].y);
}
sort(all(xs));
xs.resize(unique(all(xs)) - xs.begin());
ll sum1 = 0, sum2 = 0, mid = 0;
ll cnt1 = 0, cnt2 = 0, cntmid = 0;
map<int, int> coords;
for (int x: xs)
coords[x] = 0;
int tt = 0;
for (auto &[x, y]: coords)
y = tt++;
for (int i = 0; i < n; i++){
sum2 += poses[i].x + poses[i].y;
cnt2++;
start[coords[poses[i].x]].push_back(i);
stop[coords[poses[i].y]].push_back(i);
}
for (int i = 0; i < sz(xs); i++){
ll pos = xs[i];
for (int j: start[i]){
auto [x, y] = poses[j];
sum2 -= x + y;
mid += abs(x - y);
cnt2--;
cntmid++;
}
for (int j: stop[i]){
auto [x, y] = poses[j];
mid -= abs(x - y);
sum1 += x + y;
cntmid--;
cnt1++;
}
ans = min(ans, 2 * pos * cnt1 - sum1 + mid + sum2 - 2 * pos * cnt2);
}
return ans + n;
}
ll res[MAXN];
ll solve2(int n){
if (n == 0)
return 0;
if (n == 1)
return poses[0].y - poses[0].x + 1;
sort(poses, poses + n, [&](pt a, pt b){return a.x + a.y < b.x + b.y;});
multiset<int> l, r;
ll sl, sr;
sl = sr = 0;
ll ans = 1e18;
for (int i = 0; i < n; i++){
auto [x1, x2] = poses[i];
for (int x: {x1, x2}) {
if (i == 0 || x >= *r.begin()) {
r.insert(x);
sr += x;
} else {
l.insert(x);
sl += x;
}
}
while (sz(l) < sz(r)){
int x = *r.begin();
r.erase(r.begin());
sr -= x;
l.insert(x);
sl += x;
}
while (sz(l) > sz(r) + 1){
int x = *(--l.end());
l.erase(--l.end());
sl -= x;
r.insert(x);
sr += x;
}
ll x = *(--l.end());
ll curr = x * sz(l) - sl + sr - x * sz(r);
res[i] = curr;
}
l.clear();
r.clear();
sl = sr = 0;
for (int i = n - 1; i > 0; i--){
auto [x1, x2] = poses[i];
for (int x: {x1, x2}) {
if (i == 0 || x >= *r.begin()) {
r.insert(x);
sr += x;
} else {
l.insert(x);
sl += x;
}
}
while (sz(l) < sz(r)){
int x = *r.begin();
r.erase(r.begin());
sr -= x;
l.insert(x);
sl += x;
}
while (sz(l) > sz(r) + 1){
int x = *(--l.end());
l.erase(--l.end());
sl -= x;
r.insert(x);
sr += x;
}
ll x = *(--l.end());
ll curr = x * sz(l) - sl + sr - x * sz(r);
res[i - 1] += curr;
}
for (int i = 0; i < n - 1; i++)
ans = min(ans, res[i]);
return ans + n;
}
void run() {
int k, n;
k = 2;
n = 1e5;
cin >> k >> n;
ll var = 0;
int tt = 0;
for (int i = 0; i < n; i++){
char c1, c2;
int pos1, pos2;
c1 = 'A', c2 = 'B';
pos1 = rnd() % 1000000000, pos2 = rnd() % 1000000000;
cin >> c1 >> pos1 >> c2 >> pos2;
if (pos1 > pos2)
swap(pos1, pos2);
if (c1 == c2){
var += abs(pos1 - pos2);
} else {
poses[tt++] = {pos1, pos2};
}
}
n = tt;
if (k == 1){
cout << var + solve1(n) << '\n';
} else {
cout << var + solve2(n) << '\n';
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#else
fastio();
//freopen("", "r", stdin);
//freopen("", "w", stdout);
#endif
auto start = chrono::high_resolution_clock::now();
run();
auto stop = chrono::high_resolution_clock::now();
#ifdef LOCAL
cerr << "\nProgram finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec\n";
#endif
return 0;
}
