#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int, int>
const int MAX_N = 2e5+25;
ll n, k;
vector<pair<ll, pair<ll, ll>>> v;
vector<pair<ll, ll>> vtx;
ll sum = 0;
multiset<ll> a, b;
multiset<ll> c, d;
ll suma, sumb, sumc, sumd;
ll mini = 1e18;
void print() {
ll res = 0;
ll p1 = 0;
ll p2 = 0;
ll p3 = 0;
ll p4 = 0;
if(a.size() > 0)
p1 = ((*a.rbegin()) * a.size()) - suma;
if(b.size() > 0)
p2 = sumb - ((*a.rbegin()) * b.size());
if(c.size() > 0)
p3 += ((*c.rbegin()) * c.size()) - sumc;
if(d.size() > 0)
p4 += sumd - ((*c.rbegin()) * d.size());
res = p1 + p2 + p3 + p4;
mini = min(mini, res);
}
void handle(multiset<ll> & s, multiset<ll> & f, ll & sum1, ll & sum2) {
while(s.size() > f.size() && s.size() - f.size() >= 2) {
ll x = *s.rbegin();
sum1 -= x;
sum2 += x;
s.erase(s.find(x));
f.insert(x);
}
while(f.size() > s.size()) {
ll x = *f.begin();
sum1 += x;
sum2 -= x;
f.erase(f.begin());
s.insert(x);
}
}
void add(int y) {
if(a.size() == 0) {
a.insert(y);
suma += y;
}
else {
if(y > *a.rbegin()) {
sumb += y;
b.insert(y);
}
else {
suma += y;
a.insert(y);
}
}
if(y > *c.rbegin()) {
d.erase(d.find(y));
sumd -= y;
}
else {
sumc -= y;
c.erase(c.find(y));
}
handle(a, b, suma, sumb);
handle(c, d, sumc, sumd);
}
void solve() {
sort(v.begin(), v.end());
for(auto i : v) {
vtx.pb({i.second.first, i.second.second});
}
for(auto i : vtx) {
c.insert(i.first);
c.insert(i.second);
sumc += i.first;
sumc += i.second;
}
handle(c, d, sumc, sumd);
print();
for(int i = 0; i < vtx.size(); i++) {
add(vtx[i].first);
add(vtx[i].second);
print();
}
}
void input() {
cin >> k >> n;
if(k == 1) {
vector<int> cnt;
for(int i = 1; i <= n; i++) {
char a, b;
ll x, y;
cin >> a >> x >> b >> y;
if(a != b) {
sum++;
cnt.pb(x);
cnt.pb(y);
}
else {
sum += abs(x - y);
}
}
sort(cnt.begin(), cnt.end());
ll mid = cnt[(cnt.size() - 1) / 2];
for(auto i : cnt) {
sum += abs(i - mid);
}
cout << sum;
}
else {
for(int i = 1; i <= n; i++) {
char a, b;
ll x, y;
cin >> a >> x >> b >> y;
if(a != b)
v.pb({x + y, {x, y}});
else
sum += abs(x - y);
}
if(v.size() == 0)
cout << sum;
else {
solve();
cout << sum + mini + v.size();
}
}
}
int main() {
faster;
input();
}
