#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 1e5+10;
const ll INF = 1e18;
ll a[N], b[N], n, k;
struct Median {
priority_queue<ll> lw;
priority_queue<ll, vector<ll>, greater<ll>> up;
ll slw, sup;
Median(): slw(0), sup(0) {}
void add(int x) {
if (!lw.empty() && lw.top() < x) up.push(x), sup+=x;
else lw.push(x), slw+=x;
while (up.size() > lw.size()) {
sup-=up.top(), slw+=up.top();
lw.push(up.top()), up.pop();
}
while (lw.size() > up.size()+1) {
slw-=lw.top(), sup+=lw.top();
up.push(lw.top()), lw.pop();
}
}
ll que() {
if (lw.empty()) return 0;
ll vl=lw.top();
return (vl*lw.size()-slw)+(sup-vl*up.size());
}
};
int main() {
cin>>k>>n;
ll ans=0;
vector<pii> v;
for (int i=1; i<=n; ++i) {
string p, s;
cin>>p>>a[i]>>s>>b[i];
if (p == s) {
ans+=abs(a[i]-b[i]);
continue;
} ++ans;
if (a[i] > b[i]) swap(a[i], b[i]);
v.push_back({a[i]+b[i], i});
} sort(v.begin(), v.end());
if (v.empty()) {
cout<<ans<<"\n";
return 0;
}
// k = 1
Median med;
for (auto u : v) med.add(a[u.second]), med.add(b[u.second]);
ll ovl=med.que();
// k = 2
if (k == 2) {
ll p[n+1]={}, suf[n+1]={}, sz=v.size();
Median lf, rf;
for (int j=0; j<sz; ++j) {
lf.add(a[v[j].second]), lf.add(b[v[j].second]);
p[j]=lf.que();
}
for (int j=sz-1; j>=0; --j) {
rf.add(a[v[j].second]), rf.add(b[v[j].second]);
suf[j]=rf.que();
}
ll g=INF;
for (int j=0; j+1<sz; ++j) g=min(g, p[j]+suf[j+1]);
ans+=min(ovl, g);
} else ans+=ovl;
cout<<ans<<"\n";
}
