#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Citizen {
char from_zone, to_zone;
int from_building, to_building;
};
ll cost_with_bridge(int a, int b, int bridge_pos) {
return abs(a - bridge_pos) + 1 + abs(b - bridge_pos);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K, N;
cin >> K >> N;
vector<Citizen> citizens(N);
vector<pair<int, int>> crossers;
ll total_cost = 0;
for (int i = 0; i < N; ++i) {
string s;
cin >> s;
citizens[i].from_zone = s[0];
int j = 1;
while (isdigit(s[j])) citizens[i].from_building = citizens[i].from_building * 10 + (s[j++] - '0');
citizens[i].to_zone = s[j++];
while (j < s.size()) citizens[i].to_building = citizens[i].to_building * 10 + (s[j++] - '0');
if (citizens[i].from_zone == citizens[i].to_zone) {
total_cost += abs(citizens[i].from_building - citizens[i].to_building);
} else {
crossers.emplace_back(citizens[i].from_building, citizens[i].to_building);
}
}
if (crossers.empty()) {
cout << total_cost << '\n';
return 0;
}
vector<int> ideal_positions;
for (auto &[a, b] : crossers) {
ideal_positions.push_back((a + b) / 2);
}
sort(ideal_positions.begin(), ideal_positions.end());
vector<int> bridge_positions;
if (K >= ideal_positions.size()) {
bridge_positions = ideal_positions;
} else {
int per_cluster = ideal_positions.size() / K;
int remainder = ideal_positions.size() % K;
int idx = 0;
for (int i = 0; i < K; ++i) {
int len = per_cluster + (i < remainder);
int mid = idx + len / 2;
bridge_positions.push_back(ideal_positions[mid]);
idx += len;
}
}
for (auto &[a, b] : crossers) {
ll best = LLONG_MAX;
for (int bridge : bridge_positions) {
best = min(best, cost_with_bridge(a, b, bridge));
}
total_cost += best;
}
cout << total_cost << '\n';
return 0;
}
