#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const ll INF = 1e18;
inline ll getmin(ll a, ll b) {
return a < b ? a : b;
}
inline void solve(vector < pair <int, int> > &arr, vector <ll> &sol) {
int sz = arr.size();
sol.resize(sz);
multiset <int> mst1, mst2;
ll sum1 = 0, sum2 = 0;
for(int i = 0; i < sz; i++) {
mst2.insert(arr[i].first);
sum2 += arr[i].first;
mst2.insert(arr[i].second);
sum2 += arr[i].second;
while(mst1.size() < i + 1) {
mst1.insert(*mst2.begin());
sum1 += *mst2.begin();
sum2 -= *mst2.begin();
mst2.erase(mst2.begin());
}
while(*prev(mst1.end()) > *mst2.begin()) {
int a = *prev(mst1.end()), b = *mst2.begin();
mst1.erase(mst1.find(a));
mst1.insert(b);
mst2.erase(mst2.find(b));
mst2.insert(a);
sum1 += b - a;
sum2 += a - b;
}
int cur = *prev(mst1.end());
sol[i] = 1LL * mst1.size() * cur - sum1 + sum2 - 1LL * mst2.size() * cur;
}
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> k >> n;
vector < pair <int, int> > arr;
ll ans = 0;
for(i = 1; i <= n; i++) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if(x > y) {
swap(x, y);
}
if(a != b) {
arr.push_back({x, y});
}
else {
ans += y - x;
}
}
sort(arr.begin(), arr.end(), [&](const pair <int, int> &a, const pair <int, int> &b) {
return a.first + a.second < b.first + b.second;
});
if(arr.size() == 0) {
cout << ans;
return 0;
}
if(k == 1) {
vector <int> vals;
ll tot = 0;
for(auto it : arr) {
vals.push_back(it.first);
vals.push_back(it.second);
tot += it.first + it.second;
}
sort(vals.begin(), vals.end());
int sz = arr.size();
ll mn = INF, sum = 0;
for(i = 0; i < 2 * sz; i++) {
mn = getmin(mn, 1LL * vals[i] * i - sum + (tot - sum) - 1LL * vals[i] * (2 * sz - i));
sum += vals[i];
}
cout << ans + mn + sz;
return 0;
}
vector <ll> sol_l, sol_r;
solve(arr, sol_l);
reverse(arr.begin(), arr.end());
solve(arr, sol_r);
int sz = arr.size();
ll mn = getmin(sol_l[sz - 1], sol_r[sz - 1]);
for(int i = 0; i < sz - 1; i++) {
mn = getmin(mn, sol_l[i] + sol_r[sz - i - 2]);
}
cout << ans + mn + sz;
//cin.close();
//cout.close();
return 0;
}
