#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K, N;
cin >> K >> N;
vector<ll> same_zone;
vector<ll> cross_values;
for (int i = 0; i < N; ++i) {
string p, q;
cin >> p >> q;
char Pi = p[0];
ll Si = stoll(p.substr(1));
char Qi = q[0];
ll Ti = stoll(q.substr(1));
if (Pi == Qi) {
same_zone.push_back(abs(Si - Ti));
} else {
cross_values.push_back(Si + Ti);
}
}
ll total = 0;
for (ll d : same_zone) total += d;
if (cross_values.empty() || K == 0) {
total += cross_values.size();
cout << total << '\n';
return 0;
}
sort(cross_values.begin(), cross_values.end());
if (K == 1) {
ll median = cross_values[cross_values.size() / 2];
for (ll x : cross_values) {
total += abs(x - 2 * (median / 2)) + 1;
}
cout << total << '\n';
return 0;
}
int m = cross_values.size();
vector<ll> prefix(m + 1), suffix(m + 1);
for (int i = 0; i < m; ++i)
prefix[i + 1] = prefix[i] + cross_values[i];
for (int i = m - 1; i >= 0; --i)
suffix[i] = suffix[i + 1] + cross_values[i];
ll best = 1e18;
for (int split = 0; split <= m; ++split) {
// left [0, split - 1], right [split, m - 1]
ll left_cost = 0;
if (split > 0) {
int mid = split / 2;
ll median = cross_values[mid];
for (int i = 0; i < split; ++i) {
left_cost += abs(cross_values[i] - median);
}
}
ll right_cost = 0;
if (split < m) {
int len = m - split;
int mid = split + len / 2;
ll median = cross_values[mid];
for (int i = split; i < m; ++i) {
right_cost += abs(cross_values[i] - median);
}
}
best = min(best, left_cost + right_cost + m);
}
cout << total + best << '\n';
return 0;
}
