#include <bits/stdc++.h>
#define int long long
using namespace std;
int alg(const vector<int>& ps) {
int sz=ps.size();
if (sz<=1) return 0;
int first_sum=ps[sz/2];
int second_sum=ps[sz-1]-ps[sz/2];
return second_sum-first_sum;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("1.in","r",stdin);
int k,n;
cin >> k >> n;
if (k==1) {
int ans=0;
vector<int> coord;
coord.reserve(2*n);
for (int i=0;i<n;i++) {
char c1,c2;
int x,y;
cin >> c1 >> x >> c2 >> y;
if (c1==c2) ans+=abs(x-y);
else {
coord.push_back(x);
coord.push_back(y);
}
}
ans+=coord.size()/2;
sort(coord.begin(),coord.end());
vector<int> ps(coord.size()+1,0);
for (int i=0;i<coord.size();i++) {
ps[i+1]=ps[i]+coord[i];
}
cout<<ans+alg(ps)<<"\n";
return 0;
}
else if (k==2) {
int ans=0;
vector<pair<int,int>> vp;
vp.reserve(n);
for (int i=0;i<n;i++) {
char c1,c2;
int x,y;
cin >> c1 >> x >> c2 >> y;
if (c1==c2) ans+=abs(x-y);
else vp.push_back({x,y});
}
sort(vp.begin(),vp.end(),[](const pair<int,int>& a, const pair<int,int>& b){return a.first+a.second<b.first+b.second;});
vector<int> coord(vp.size()*2);
for (int i=0;i<vp.size();i++) {
coord[i*2]=vp[i].first;
coord[i*2+1]=vp[i].second;
}
ans+=coord.size()/2;
if (coord.size()<=2) {
cout<<ans<<"\n";
return 0;
}
vector<int> ps(coord.size()+1,0);
for (int i=0;i<coord.size();i++) {
ps[i+1]=ps[i]+coord[i];
}
// for (auto num:coord) cout<<num<<" ";
// cout<<"\n";
// for (auto num:ps) cout<<num<<" ";
// cout<<"\n";
int temp=1e18;
for (int i=2;i<=coord.size()-2;i+=2){
vector<int> v1(coord.begin(),coord.begin()+i);
vector<int> v2(coord.begin()+i,coord.end());
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
vector<int> ps1(v1.size()+1,0);
vector<int> ps2(v2.size()+1,0);
for (int j=0;j<v1.size();j++) {
ps1[j+1]=ps1[j]+v1[j];
}
for (int j=0;j<v2.size();j++) {
ps2[j+1]=ps2[j]+v2[j];
}
temp=min(temp,alg(ps1)+alg(ps2));
}
cout<<ans+temp<<"\n";
return 0;
}
}
