#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define SZ(x) ll(x.size())
const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
ll k , n , ans , pref[MAXN] , suff[MAXN] , ps[MAXN] , sum;
priority_queue<ll> pq;
priority_queue<ll , vector<ll> , greater<ll>> pq2;
vector<pll> vec;
void insert(ll x){
if(SZ(pq) && x < pq.top()) pq.push(x) , sum -= x;
else pq2.push(x) , sum += x;
while(SZ(pq) > SZ(pq2)){
x = pq.top(); pq.pop(); pq2.push(x);
sum += 2 * x;
}
while(SZ(pq2) > SZ(pq) + 1){
x = pq2.top(); pq2.pop(); pq.push(x);
sum -= 2 * x;
}
assert(SZ(pq2) >= SZ(pq));
assert(SZ(pq) == 0 || pq2.top() >= pq.top());
// exit(0);
}
ll solve(){
ll x = pq2.top();
return sum + x * (SZ(pq) - SZ(pq2));
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> k >> n;
for(int i = 0 ; i < n ; i++){
string A , B;
int x , y;
cin >> A >> x >> B >> y;
if(A == B){
ans += abs(x - y);
continue;
}
ans++;
vec.push_back({x + y , y});
}
if(SZ(vec) == 0) return cout << ans << endl , 0;
sort(all(vec));
n = SZ(vec);
// pq.push(1)a; pq.push(1);
// cout << SZ(pq) << endl;
for(int i = 0 ; i < n ; i++){
insert(vec[i].X - vec[i].Y);
insert(vec[i].Y);
pref[i] = solve();
}
pq = {}; pq2 = {}; sum = 0;
for(int i = n - 1 ; i >= 0 ; i--){
insert(vec[i].X - vec[i].Y);
insert(vec[i].Y);
suff[i] = solve();
}
ll res = pref[n - 1] + ans;
for(int i = 0 ; i + 1 < n && k == 2 ; i++){
res = min(res , pref[i] + suff[i + 1] + ans);
}
cout << res << endl;
return 0;
}
/*
*/
