//#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 ans = 0, additional = 0;
for (int i = 0; i < n; ++i) {
string s1, s2;
int x, y;
cin >> s1 >> x >> s2 >> y;
if (x > y) swap(x, y);
if (s1 == s2) {
additional += y - x;
--i, --n;
continue;
}
additional += 1;
A[i] = x, B[i] = y;
}
if (n == 0) {
cout << additional;
return 0;
}
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [](int i, int j) {
return A[i] + B[i] < A[j] + B[j];
});
//note that we choose to go to L if A + B <= L + R, and to R otherwise
multiset<int> L, R;
ll sum[2] = {0, 0};
int mid = 0;
auto add = [&L, &R, &mid, &sum](int x) {
if (x < mid) {
L.insert(x);
sum[0] += x;
} else {
R.insert(x);
sum[1] += x;
}
if (sz(L) > sz(R)) {
int v = *L.rbegin();
L.extract(v);
sum[0] -= v;
sum[1] += v;
mid = v;
R.insert(v);
} else if (sz(R) > sz(L)) {
int v = *R.begin();
R.erase(R.begin());
sum[1] -= v;
sum[0] += v;
mid = v;
L.insert(v);
}
};
vector<ll> pref(n), suf(n);
for (int j = 0; j < n; ++j) {
int i = ord[j];
add(A[i]);
add(B[i]);
pref[j] = (mid * (ll) sz(L) - sum[0]) + (sum[1] - (mid * (ll) sz(R)));
}
L.clear(), R.clear(), sum[0] = sum[1] = mid = 0;
for (int j = n - 1; j > -1; --j) {
int i = ord[j];
add(A[i]);
add(B[i]);
suf[j] = (mid * (ll) sz(L) - sum[0]) + (sum[1] - (mid * (ll) sz(R)));
}
ans = suf[0];
if (k == 2) {
for (int i = 1; i < n; ++i) {
ckmn(ans, pref[i - 1] + suf[i]);
}
}
cout << ans + additional;
return 0;
}
