#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
vector<pair<int, int> > eve;
vector<ll> places;
ll Answer = inf;
vector<ll> seg[4 * maxn], par[4 * maxn];
void build(int id, int L, int R){
if (L + 1 == R){
seg[id].push_back(eve[L].first);
seg[id].push_back(eve[L].second);
sort(seg[id].begin(), seg[id].end());
par[id].push_back(seg[id][0]);
par[id].push_back(seg[id][0] + seg[id][1]);
return;
}
int mid = (L + R) >> 1;
build(2 * id + 0, L, mid);
build(2 * id + 1, mid, R);
for (int i = 0; i < seg[2 * id + 0].size(); i++)
seg[id].push_back(seg[2 * id + 0][i]);
for (int i = 0; i < seg[2 * id + 1].size(); i++)
seg[id].push_back(seg[2 * id + 1][i]);
sort(seg[id].begin(), seg[id].end());
par[id].push_back(seg[id][0]);
for (int i = 1; i < seg[id].size(); i++)
par[id].push_back(par[id].back() + seg[id][i]);
}
ll get(int id, int L, int R, int l, int r, int x){
if (L == l and R == r){
// cout << "Get : " << L << " " << R << " " << x << endl;
// for (auto it : seg[id])
// cout << it << " ";
// cout << endl;
int idx = upper_bound(seg[id].begin(), seg[id].end(), x) - seg[id].begin() - 1;
// cout << idx << " -> " << endl;
if (idx < 0)
return par[id].back() - 1ll * seg[id].size() * x;
if (idx == seg[id].size() - 1)
return 1ll * seg[id].size() * x - par[id].back();
ll pre = 1ll * x * (idx + 1) - par[id][idx];
ll suf = (par[id].back() - par[id][idx]) - 1ll * (seg[id].size() - idx - 1) * x;
// cout << pre << " " << suf << endl;
return pre + suf;
}
ll sum = 0;
int mid = (L + R) >> 1;
if (l < mid)
sum += get(2 * id + 0, L, mid, l, min(mid, r), x);
if (mid < r)
sum += get(2 * id + 1, mid, R, max(l, mid), r, x);
return sum;
}
bool cmp(pair<int,int> fi, pair<int, int> se){
return fi.first + fi.second < se.first + se.second;
}
ll calculate(int i, int j){
int k = (places[i] + places[j]);
int lo = -1, hi = eve.size();
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (eve[mid].first + eve[mid].second <= k)
lo = mid;
else
hi = mid;
}
int q = eve.size();
ll sum = 0;
if (hi > 0)
sum += get(1, 0, q, 0, hi, places[i]);
if (hi != q)
sum += get(1, 0, q, hi, q, places[j]);
// cout << places[i] << " " << places[j] << " lo is : " << lo << " -> " << sum << endl;
return sum;
}
void find(int L, int R, int l, int r){
if (L >= R)
return;
int mid = (L + R) >> 1;
ll k = inf, idx = -1;
for (int i = l; i < min(mid, r); i++){
ll tmp = calculate(i, mid);
if (tmp < k){
k = tmp;
idx = i;
}
}
Answer = min(Answer, k);
find(L, mid, l, idx + 1);
find(mid + 1, R, idx, r);
}
ll solve(){
int n = eve.size();
vector<ll> a(2 * n + 1);
for (int i = 0; i < n; i++){
a[2 * i + 0 + 1] = eve[i].first;
a[2 * i + 1 + 1] = eve[i].second;
}
sort(a.begin() + 1, a.end());
n = 2 * n;
for (int i = 1; i <= n; i++)
a[i] += a[i - 1];
ll answer = inf;
for (int i = 1; i <= n; i++){
ll T = a[i] - a[i - 1];
answer = min(answer, T * (i - (n - i)) - a[i] + (a[n] - a[i]));
}
return answer + eve.size();
}
int main(){
ios_base::sync_with_stdio(false);
int k, n;
cin >> k >> n;
ll answer = 0;
for (int i = 0; i < n; i++){
int x, y;
char a, b;
cin >> a >> x >> b >> y;
if (a == b){
answer += abs(x - y);
continue;
}
if (a == 'B')
swap(x, y);
eve.push_back({x, y});
}
if (eve.empty())
return cout << answer << endl, 0;
if (k == 1){
cout << answer + solve() << '\n';
return 0;
}
for (int i = 0; i < eve.size(); i++){
places.push_back(eve[i].first);
places.push_back(eve[i].second);
}
sort(places.begin(), places.end());
int m = places.size();
int q = eve.size();
sort(eve.begin(), eve.end(), cmp);
build(1, 0, q);
find(0, m, 0, m);
cout << Answer + answer + eve.size() << endl;
return 0;
}
