#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define int long long
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define sp <<" "<<
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define DEBUG(x) cout<<#x sp x<<endl;
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define mid (l+r)/2
const int MAXN=3e4+5;
const int MOD=1e9+7;
const int INF=1e18;
map<int,vi> tut;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>k>>n;
vector<char> p(n+1), q(n+1);
vi s(n+1), t(n+1);
set<int> cur;
int ans=0;
int top=0;
int tt=0;
FORE(i,1,n+1){
cin>>p[i]>>s[i]>>q[i]>>t[i];
cur.insert(s[i]);
cur.insert(t[i]);
if(p[i]!=q[i]){
top+=t[i]+s[i];
tt+=2;
tut[s[i]].pb(i);
tut[t[i]].pb(i);
}
else ans+=abs(t[i]-s[i]);
}
vi vec;
for(auto el:cur) vec.pb(el);
int sz=vec.size();
int res=INF;
if(k<=2){
int say=0;
int tane=0;
FOR(i,sz){ //vec[i] de ise köprü
say+=tut[vec[i]].size()*vec[i];
tane+=tut[vec[i]].size();
res=min(res,tane*vec[i]-say+(top-say)-((tt-tane)*vec[i]));
}
}
if(k==2){
int say,say2,tane,tane2;
say=say2=tane=tane2=0;
set<int> bir;
FOR(i,sz){ //vec[i] de ise köprü
say+=tut[vec[i]].size()*vec[i];
tane+=tut[vec[i]].size();
for(auto el:tut[vec[i]]){
if(bir.count(el)){
say2-=t[el];
tane2--;
}
else{
say2+=t[el];
tane2++;
}
bir.insert(el);
}
int deg=tane*vec[i]-say+say2-(tane2*vec[i]);
//cout<<"here" sp vec[i] sp say sp tane<<endl;
int say3,tane3;
say3=tane3=0;
set<int> iki;
FORE(j,i+1,sz){
for(auto el:tut[vec[j]]){
if(bir.count(el)) continue;
if(iki.count(el)){
//ya 1. ya 2. köprüye gidecekler
if(t[el]+s[el]-2*vec[i]<2*vec[j]-(t[el]+s[el])){
say2+=vec[j];
tane2++;
}
else{
say3+=vec[j];
tane3++;
}
}
else{
say3+=vec[j];
tane3++;
}
}
int deg2=tane3*vec[j]-say3;
int deg3=(top-say-say2-say3)-(tt-tane-tane2-tane3)*vec[j];
res=min(res,deg+deg2+deg3);
}
}
}
cout<<ans+res+tt/2<<endl;
}
