#include <bits/stdc++.h>
using namespace std;
priority_queue <long long> leftBridge;
priority_queue <long long, vector <long long>, greater <long long>> rightBridge;
long long leftSum = 0, rightSum = 0;
bool comparePriority(pair <long long, long long> firstCitizen, pair <long long, long long> secondCitizen) {
return (firstCitizen.first + firstCitizen.second < secondCitizen.first + secondCitizen.second);
}
void insertCitizen(long long placeCoordinate) {
long long median = leftBridge.empty() ? LLONG_MAX : leftBridge.top();
if (placeCoordinate <= median) {
leftBridge.push(placeCoordinate);
leftSum += placeCoordinate;
} else {
rightBridge.push(placeCoordinate);
rightSum += placeCoordinate;
}
int numCitizensInLeft = (int) leftBridge.size();
int numCitizensInRight = (int) rightBridge.size();
if (numCitizensInRight + 1 < numCitizensInLeft) {
long long largestSmaller = leftBridge.top();
leftBridge.pop();
rightBridge.push(largestSmaller);
leftSum -= largestSmaller;
rightSum += largestSmaller;
} else if (numCitizensInLeft < numCitizensInRight) {
long long smallestLarger = rightBridge.top();
rightBridge.pop();
leftBridge.push(smallestLarger);
rightSum -= smallestLarger;
leftSum += smallestLarger;
}
}
void reset() {
priority_queue <long long> emptyFirst;
swap(leftBridge, emptyFirst);
priority_queue <long long, vector <long long>, greater <long long>> emptySecond;
swap(rightBridge, emptySecond);
leftSum = rightSum = 0;
}
int main() {
int maxNumBridge, numCitizens;
cin >> maxNumBridge >> numCitizens;
vector <pair <long long, long long>> listPairOpposite = {{0, 0}};
char firstPlace, secondPlace;
long long firstPosition, secondPosition;
long long actualSameSide = 0;
while (numCitizens--) {
cin >> firstPlace >> firstPosition >> secondPlace >> secondPosition;
if (firstPlace == secondPlace) // Not consider because they need not use bridge
actualSameSide += abs(firstPosition - secondPosition);
else
listPairOpposite.push_back(pair <long long, long long> {firstPosition, secondPosition});
}
// Soft by sum of 2 position (median)
sort(listPairOpposite.begin(), listPairOpposite.end(), comparePriority);
// All other cases must be cross bridges
numCitizens = (int) listPairOpposite.size() - 1;
actualSameSide += numCitizens;
vector <long long> maxSumAbs(numCitizens + 1, 0);
for (int indexOfCitizen = 1; indexOfCitizen <= numCitizens; indexOfCitizen++) {
insertCitizen(listPairOpposite[indexOfCitizen].first);
insertCitizen(listPairOpposite[indexOfCitizen].second);
maxSumAbs[indexOfCitizen] = rightSum - leftSum;
}
long long actualSumAcross = maxSumAbs[numCitizens];
if (maxNumBridge == 2) {
reset();
for (int indexOfCitizen = numCitizens; indexOfCitizen >= 0; indexOfCitizen--) {
insertCitizen(listPairOpposite[indexOfCitizen].first);
insertCitizen(listPairOpposite[indexOfCitizen].second);
// listPairOpposite[indexOfCitizen ... numCitizens] in left. Other in right of bridge 2
actualSumAcross = min(actualSumAcross, rightSum - leftSum + maxSumAbs[indexOfCitizen - 1]);
}
}
cout << actualSameSide + actualSumAcross;
return 0;
}
