#include<bits/stdc++.h>
using namespace std;
#define _ int v, int tl, int tr, int l, int r, int h
#define tm (tl + tr >> 1)
#define sol L[h][v],tl,tm,l,r,h
#define sag R[h][v],tm+1,tr,l,r,h
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < ll , ll > pp;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
ll root[2][N],L[2][N*20],R[2][N*20],w,id[2],A[N],a;
ll dp[N],tp[N],W[N];
pp s[2][N*20];
char c1,c2;
pp mrg(pp a, pp b){
return mp(a.st+b.st , a.nd+b.nd);
}
int up(_, int x){
if(tl > r || tr < l) return v;
int nw = ++id[h];
if(!(tl >= l && tr <= r)) { L[h][nw] = up(sol,x); R[h][nw] = up(sag,x); }
s[h][nw] = mrg(s[h][v] , mp(x,1));
return nw;
}
pp qry(_){
if(tl > r || tr < l || !v) return mp(0,0);
if(tl >= l && tr <= r) return s[h][v];
return mrg( qry(sol) , qry(sag) );
}
void f(int l, int r, int opl, int opr){
if(l > r) return;
ll t;
int op, m = l+r >> 1;
pp x;
for(int i=max(m+1,opl); i<=opr; i++){
int mid = upper_bound(A+1 , A+a+1 , W[m]+W[i]) - A;
x = qry(root[0][mid-1],1,w,m,w,0);
t = dp[i] + x.st - x.nd*W[m];
x = qry(root[1][mid],1,w,1,i,1);
t += x.nd*W[i] - x.st;
//cout << m << " " << i << " --->>> " << mid << " " << t << " aa\n";
if(tp[m] > t) { tp[m] = t; op = i; }
}
if(l == r) return;
f(l,m-1,opl,op); f(m+1,r,op,opr);
}
map < int , vector < pp > > M;
map < int , ll > H,H2;
ll n,k,i,j,p,x,y,z,ans = 1LL << 55;
int main(){
cin >> k >> n;
for(i=1;i<=n;i++){
scanf(" %c%lld %c%lld",&c1,&x,&c2,&y);
if(x > y) swap(x,y); z += y-x;
if(c1 == c2) continue;
z++;
H[y]++;
M[x+y].pb(mp(x,y));
if(M[x+y].size() == 1) A[++a] = x+y;
if(!H2[x]) { H2[x] = 1; W[++w] = x; }
if(!H2[y]) { H2[y] = 1; W[++w] = y; }
}
sort(W+1 , W+w+1);
sort(A+1 , A+a+1);
for(p=0,i=a; i ;i--){
y = A[i];
for(auto x : M[y]){
j = lower_bound(W+1 , W+w+1 , x.nd) - W;
p = up(p,1,w,j,j,1,x.nd);
}
root[1][i] = p;
} root[1][0] = p;
for(p=0,i=1;i<=a;i++){
//cout << A[i] << " ";
y = A[i];
for(auto x : M[y]){
j = lower_bound(W+1 , W+w+1 , x.st) - W;
p = up(p,1,w,j,j,0,x.st);
}
root[0][i] = p;
}
// puts(" aa");
root[0][a+1] = p;
memset(dp , 22 , sizeof dp);
W[w+1] = 1LL << 55;
dp[w+1] = 0;
for(; k-- ;){
memset(tp , 22 , sizeof tp);
f(1,w,1,w+1);
for(i=1;i<=w;i++){
dp[i] = tp[i];
//cout << k << " " << i << " " << dp[i] << " ss\n";
}
}
x=y=0;
for(i=1;i<=w;i++){
ll w = W[i];
x += H[w]*w;
y += H[w];
//cout << i << " " << dp[i] + y*W[i] - x << " ans\n";
ans = min(ans , dp[i] + y*w - x);
}
cout << z + (w ? ans + ans : 0);
return 0;
}
