/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <istream>
#include <queue>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define myassert(Expr, Msg) ;
#endif
int _n, _k;
ll ans = INFll, sum = 0, suml, sumr;
vector<pair<int, int>> V;
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<>> rpq;
inline void systemd() {
sum = suml = sumr = 0;
}
void insert(int x) {
int med = (lpq.size() ? lpq.top() : INFi + 1);
if (x <= med) {
lpq.push(x);
suml += x;
} else {
rpq.push(x);
sumr += x;
}
if (lpq.size() < rpq.size()) {
int x = rpq.top();
rpq.pop();
suml += x;
sumr -= x;
lpq.push(x);
} else if (lpq.size() != rpq.size() && lpq.size() - 1 != rpq.size()) {
int x = lpq.top();
lpq.pop();
suml -= x;
sumr += x;
rpq.push(x);
}
}
char solve() {
if (!(cin >> _k >> _n))
return 1;
systemd();
for (size_t i = 0; i < _n; i++) {
char q, w;
int e, r;
cin >> q >> e;
cin >> w >> r;
if (q == w) {
sum += abs(e - r);
} else {
V.push_back(make_pair(e, r));
sum++;
}
}
sort(V.begin(), V.end(), [&](const pair<int, int> &l, const pair<int, int> &r) {
return l.first + l.second < r.first + r.second;
});
dbg(V);
_n = V.size();
vector<ll> pref(_n + 1, 0);
for (size_t i = 0; i < _n; i++) {
insert(V[i].first);
insert(V[i].second);
pref[i + 1] = sumr - suml;
dbg(make_pair(suml, sumr));
}
dbg(pref);
dbg(make_pair(suml, sumr));
dbg(sumr - suml);
dbg(sum);
ans = sumr - suml;
dbg(ans);
if (_k == 2) {
// lpq.clear(); WTF??
while (lpq.size()) {
lpq.pop();
}
while (rpq.size()) {
rpq.pop();
}
suml = sumr = 0;
for (int i = _n - 1; i >= 0; --i) {
insert(V[i].first);
insert(V[i].second);
ans = min(ans, sumr - suml + pref[i]);
}
}
cout << ans + sum << ln;
return 0;
}
// Attack on titan<3
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t = 1e9;
// cin >> t;
for (int cases = 0; cases < t; cases++) {
if (solve())
break;
#ifdef ONPC
cerr << "__________\n";
#endif
}
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
