#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;
}
multiset<int> low_ms1, high_ms1, low_ms2, high_ms2;
int low_sum1=0, high_sum1=0, low_sum2=0, high_sum2=0;
vector<int> temp_coord=coord;
sort(temp_coord.begin(),temp_coord.end());
for (int i=0;i<temp_coord.size();i++) {
if (i<temp_coord.size()/2) {
low_ms2.insert(temp_coord[i]);
low_sum2+=temp_coord[i];
}
else {
high_ms2.insert(temp_coord[i]);
high_sum2+=temp_coord[i];
}
}
// for (auto num: coord) cout<<num<<" ";
// cout<<"\n";
int temp_sum=1e18;
for (int i=0;i<coord.size()-4;i+=2) {
int num1=coord[i], num2=coord[i+1];
if (low_ms1.empty()){
low_ms1.insert(min(num1,num2));
high_ms1.insert(max(num1,num2));
low_sum1+=min(num1,num2);
high_sum1+=max(num1,num2);
}
else {
if (num1<=*low_ms1.rbegin()) {
low_ms1.insert(num1);
low_sum1+=num1;
}
else {
high_ms1.insert(num1);
high_sum1+=num1;
}
if (num2<=*low_ms1.rbegin()) {
low_ms1.insert(num2);
low_sum1+=num2;
}
else {
high_ms1.insert(num2);
high_sum1+=num2;
}
}
if (low_ms1.size()>high_ms1.size()) {
high_sum1+=*low_ms1.rbegin();
high_ms1.insert(*low_ms1.rbegin());
low_sum1-=*low_ms1.rbegin();
low_ms1.erase(prev(low_ms1.end()));
}
else if (low_ms1.size()<high_ms1.size()) {
low_sum1+=*high_ms1.begin();
low_ms1.insert(*high_ms1.begin());
high_sum1-=*high_ms1.begin();
high_ms1.erase(high_ms1.begin());
}
if (num1<=*low_ms2.rbegin()) {
low_ms2.erase(low_ms2.find(num1));
low_sum2-=num1;
}
else {
high_ms2.erase(high_ms2.find(num1));
high_sum2-=num1;
low_ms2.insert(num1);
}
if (num2<=*low_ms2.rbegin()) {
low_ms2.erase(low_ms2.find(num2));
low_sum2-=num2;
}
else {
high_ms2.erase(high_ms2.find(num2));
high_sum2-=num2;
low_ms2.insert(num2);
}
if (low_ms2.size()>high_ms2.size()) {
high_sum2+=*low_ms2.rbegin();
high_ms2.insert(*low_ms2.rbegin());
low_sum2-=*low_ms2.rbegin();
low_ms2.erase(prev(low_ms2.end()));
}
else if (low_ms2.size()<high_ms2.size()) {
low_sum2+=*high_ms2.begin();
low_ms2.insert(*high_ms2.begin());
high_sum2-=*high_ms2.begin();
high_ms2.erase(high_ms2.begin());
}
//cout<<i<<" "<<low_sum1<<" "<<high_sum1<<" "<<low_sum2<<" "<<high_sum2<<"\n";
temp_sum=min(temp_sum,high_sum1-low_sum1+high_sum2-low_sum2);
}
cout<<ans+temp_sum<<"\n";
return 0;
}
}
