#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
// A data structure to maintain the median and the sum of absolute differences
// to the median in O(log N) time per insertion.
struct MedianTracker {
priority_queue<long long> left_pq; // Max-heap for the smaller half
priority_queue<long long, vector<long long>, greater<long long>> right_pq; // Min-heap for the larger half
long long sum_left = 0, sum_right = 0;
void insert(long long x) {
if (left_pq.empty() || x <= left_pq.top()) {
left_pq.push(x);
sum_left += x;
} else {
right_pq.push(x);
sum_right += x;
}
balance();
}
void balance() {
if (left_pq.size() > right_pq.size() + 1) {
long long val = left_pq.top();
left_pq.pop();
sum_left -= val;
right_pq.push(val);
sum_right += val;
} else if (right_pq.size() > left_pq.size()) {
long long val = right_pq.top();
right_pq.pop();
sum_right -= val;
left_pq.push(val);
sum_left += val;
}
}
long long get_cost() {
if (left_pq.empty()) return 0;
long long cost = sum_right - sum_left;
// If there's an odd number of elements, the median is left_pq.top()
// It needs to be balanced out from the difference calculation
if (left_pq.size() > right_pq.size()) {
cost += left_pq.top();
}
return cost;
}
};
int main() {
// Optimize standard I/O operations for performance
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int K, N;
if (!(cin >> K >> N)) return 0;
long long base_cost = 0;
// Store sum of coordinates (to sort by midpoint) and the {start, end} pair
vector<pair<long long, pair<long long, long long>>> crossers;
for (int i = 0; i < N; ++i) {
char P, Q;
long long S, T;
cin >> P >> S >> Q >> T;
if (P == Q) {
// Citizen stays on the same side, distance is fixed
base_cost += abs(S - T);
} else {
// Citizen must cross the river
base_cost += 1; // +1 for the width of the river itself
crossers.push_back({S + T, {S, T}});
}
}
// Edge case: No one needs to cross the river
if (crossers.empty()) {
cout << base_cost << "\n";
return 0;
}
// Sort intervals by their midpoints
sort(crossers.begin(), crossers.end());
if (K == 1) {
MedianTracker tracker;
for (const auto& c : crossers) {
tracker.insert(c.second.first);
tracker.insert(c.second.second);
}
cout << base_cost + tracker.get_cost() << "\n";
} else if (K == 2) {
int M = crossers.size();
// Calculate costs for all prefixes
vector<long long> pref_cost(M);
MedianTracker pref_tracker;
for (int i = 0; i < M; ++i) {
pref_tracker.insert(crossers[i].second.first);
pref_tracker.insert(crossers[i].second.second);
pref_cost[i] = pref_tracker.get_cost();
}
// Calculate costs for all suffixes
vector<long long> suff_cost(M + 1, 0);
MedianTracker suff_tracker;
for (int i = M - 1; i >= 0; --i) {
suff_tracker.insert(crossers[i].second.first);
suff_tracker.insert(crossers[i].second.second);
suff_cost[i] = suff_tracker.get_cost();
}
// Find the optimal split point
// Initialize with the cost of everyone just using 1 bridge
long long min_cross_cost = pref_cost[M - 1];
for (int i = 0; i < M - 1; ++i) {
min_cross_cost = min(min_cross_cost, pref_cost[i] + suff_cost[i + 1]);
}
cout << base_cost + min_cross_cost << "\n";
}
return 0;
}
