#include <bits/stdc++.h>
using namespace std;
constexpr long long INF = 1e18;
constexpr int MAXC = (int) 1e9;
struct SegTree {
SegTree(int n) {
data.resize(4 * n + 1);
}
void update(int node, int left, int right, int pos, long long value) {
if (left == right) {
data[node].first += value;
data[node].second++;
} else {
int mid = (left + right) / 2;
if (pos <= mid) update(2 * node, left, mid, pos, value);
else update(2 * node + 1, mid + 1, right, pos, value);
data[node].first = data[2 * node].first + data[2 * node + 1].first;
data[node].second = data[2 * node].second + data[2 * node + 1].second;
}
}
pair<long long, int> query(int node, int left, int right, int ql, int qr) {
if (ql > qr) {
return {0, 0};
}
if (ql <= left && right <= qr) {
return data[node];
} else {
int mid = (left + right) / 2;
pair<long long, int> L = {0, 0}, R = {0, 0};
if (ql <= mid) L = query(2 * node, left, mid, ql, qr);
if (mid < qr) R = query(2 * node + 1, mid + 1, right, ql, qr);
return {L.first + R.first, L.second + R.second};
}
}
vector<pair<long long, int>> data;
};
struct Road {
int x, y;
};
auto normalize(const vector<Road>& roads) {
vector<int> v;
for (auto& road : roads) {
v.push_back(road.x);
v.push_back(road.y);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
unordered_map<int, int> norm;
for (int i = 0; i < (int)v.size(); i++) {
norm[v[i]] = i + 1;
}
return norm;
}
void GetAnswers(vector<long long>& pref, vector<Road>& roads) {
int n = (int)roads.size() - 1;
for (int i = 1; i <= n; i++) {
if (roads[i].x > roads[i].y) {
swap(roads[i].x, roads[i].y);
}
// cerr << roads[i].x << " " << roads[i].y << " ";
}
// cerr << "\n";
pref.resize(n + 1, INF);
pref[0] = 0;
auto norm = normalize(roads);
const int MAX_VALUE = norm.size();
vector<int> realValue(MAX_VALUE + 1);
for (const auto& p : norm) {
realValue[p.second] = p.first;
}
SegTree small(MAX_VALUE), large(MAX_VALUE);
auto GetSplit = [&](int split) {
auto SMALL = small.query(1, 1, MAX_VALUE, 1, split - 1);
auto LARGE = large.query(1, 1, MAX_VALUE, split + 1, MAX_VALUE);
return 2LL * realValue[split] * SMALL.second - SMALL.first +
LARGE.first - 2LL * realValue[split] * LARGE.second;
};
long long totalDiffSum = 0;
for (int i = 1; i <= n; i++) {
long long diff = roads[i].y - roads[i].x;
totalDiffSum += diff;
small.update(1, 1, MAX_VALUE, norm[roads[i].y], roads[i].x + roads[i].y + diff);
large.update(1, 1, MAX_VALUE, norm[roads[i].x], roads[i].x + roads[i].y - diff);
int split = 0;
for (int step = 1 << 17; step; step >>= 1) {
if (split + step < MAX_VALUE && GetSplit(split + step) >= GetSplit(split + step + 1)) {
split += step;
}
}
pref[i] = GetSplit(split + 1) + totalDiffSum + i;
// cerr << realValue[split + 1] << " " << pref[i] << "\n";
}
}
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int k, n;
cin >> k >> n;
vector<Road> roads(1);
long long sameSideAnswer = 0;
for (int i = 1; i <= n; i++) {
char side1, side2;
int x, y;
cin >> side1 >> x >> side2 >> y;
if (side1 == side2) {
sameSideAnswer += llabs(x - y);
} else {
roads.push_back({x, y});
}
}
n = (int)roads.size() - 1;
sort(roads.begin() + 1, roads.end(), [](const Road& r1, const Road& r2) {
return r1.x + r1.y < r2.x + r2.y;
});
vector<long long> pref;
GetAnswers(pref, roads);
vector<long long> suff;
for (int i = 1; i < n - i + 1; i++) {
swap(roads[i], roads[n - i + 1]);
}
for (int i = 1; i <= n; i++) {
auto& road = roads[i];
road.x = MAXC - road.x;
road.y = MAXC - road.y;
}
GetAnswers(suff, roads);
long long differentSideAnswer = pref[n];
if (k == 2) {
for (int i = 0; i <= n; i++) {
differentSideAnswer = min(differentSideAnswer, pref[i] + suff[n - i]);
}
}
cout << sameSideAnswer + differentSideAnswer << "\n";
return 0;
}
