#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits> // For LLONG_MAX
using namespace std;
typedef long long ll;
struct Person {
char fromZone, toZone;
int fromPos, toPos;
};
ll distance(const Person& p, int bridgePos) {
if (p.fromZone == p.toZone) {
return abs(p.fromPos - p.toPos);
} else {
return abs(p.fromPos - bridgePos) + 1 + abs(p.toPos - bridgePos);
}
}
ll totalDistance(const vector<Person>& people, const vector<int>& bridges) {
ll sum = 0;
for (const auto& p : people) {
if (p.fromZone == p.toZone) {
sum += abs(p.fromPos - p.toPos);
} else {
ll minDist = LLONG_MAX;
for (int b : bridges) {
minDist = min(minDist, distance(p, b));
}
sum += minDist;
}
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K, N;
cin >> K >> N;
vector<Person> people(N);
vector<int> candidateBridges;
for (int i = 0; i < N; ++i) {
string s;
cin >> s;
people[i].fromZone = s[0];
int idx = 1;
while (isdigit(s[idx])) idx++;
people[i].fromPos = stoi(s.substr(1, idx - 1));
people[i].toZone = s[idx];
people[i].toPos = stoi(s.substr(idx + 1));
if (people[i].fromZone != people[i].toZone) {
candidateBridges.push_back(people[i].fromPos);
candidateBridges.push_back(people[i].toPos);
}
}
sort(candidateBridges.begin(), candidateBridges.end());
candidateBridges.erase(unique(candidateBridges.begin(), candidateBridges.end()), candidateBridges.end());
ll result = LLONG_MAX;
int m = candidateBridges.size();
// Try all combinations of up to K bridges (K <= 2)
if (K == 1) {
for (int i = 0; i < m; ++i) {
vector<int> bridges = {candidateBridges[i]};
result = min(result, totalDistance(people, bridges));
}
} else {
for (int i = 0; i < m; ++i) {
for (int j = i; j < m; ++j) {
vector<int> bridges = {candidateBridges[i], candidateBridges[j]};
result = min(result, totalDistance(people, bridges));
}
}
}
cout << result << '\n';
return 0;
}
