//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
int bit(int x, int b) {
return (x >> b) & 1;
}
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 100002;
const int mod = 998244353;
const ld eps = 1e-9;
int A[N], B[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, n;
cin >> k >> n;
ll perm = 0;
for (int i = 0; i < n; ++i) {
string s1, s2;
int x, y;
cin >> s1 >> x >> s2 >> y;
perm += abs(x - y);
if (s1 == s2) {
--i;
--n;
continue;
}
perm += 1; //from L to R or otherwise
if (x > y) swap(x, y);
A[i] = x, B[i] = y;
}
if (n == 0) {
cout << perm;
return 0;
}
ll ans = infL;
vector<array<int, 3>> v;
for (int i = 0; i < n; ++i) {
v.push_back({A[i], 0, i});
v.push_back({B[i], 1, i});
}
sort(all(v));
{
//only one bridge //x, type, i
int cnt_open = n, cnt_close = 0;
ll sum_open = accumulate(all(A), 0ll), sum_close = 0;
for (auto [x, t, i]: v) {
if (t == 0) {
--cnt_open;
sum_open -= x;
} else if (t == 1) {
++cnt_close;
sum_close += x;
}
ckmn(ans, (sum_open - cnt_open * (ll) x) + (cnt_close * (ll) x - sum_close));
}
}
if (k == 2) {
int m = sz(v);
vector<int> cntA(m + 1), cntB(m);
vector<ll> sufA(m + 1), prefB(m);
for (int i = 0; i < m; ++i) {
if (i) {
cntB[i] = cntB[i - 1];
prefB[i] = prefB[i - 1];
}
if (v[i][1]) {
++cntB[i];
prefB[i] += v[i][0];
}
}
for (int i = m - 1; i > -1; --i) {
cntA[i] = cntA[i + 1];
sufA[i] = sufA[i + 1];
if (!v[i][1]) {
++cntA[i];
sufA[i] += v[i][0];
}
}
for (int f = 0; f < m; ++f) {
ll now = v[f][0] * (ll) cntB[f] - prefB[f];
normal_queue<pair<ll, int>> pq;
ll sum = 0;
int cntt = 0;
ll sumcnt = 0;
for (int s = f + 1; s < m; ++s) {
ll nw = sufA[s] - v[s][0] * (ll) cntA[s];
if (v[s][1]) {
int i = v[s][2];
if (A[i] >= v[f][0]) {
pq.push(mp(A[i] - v[f][0] + v[s][0], i));
sumcnt += v[s][0];
cntt += 1;
}
}
while (!pq.empty() && pq.top().first <= v[s][0]) {
cntt -= 1;
int i = pq.top().second;
sumcnt -= B[i];
sum += A[i] - v[f][0];
pq.pop();
}
ckmn(ans, nw + now + sum + (cntt * (ll)v[s][0] - sumcnt));
}
}
}
cout << ans * 2 + perm;
return 0;
}
