#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// why would anyone write this
const int N = (int)1e5 + 10;
const int M = N * 2;
vector<int> uni;
int id(int x){
return lower_bound(uni.begin(), uni.end(), x) - uni.begin();
}
ll pf[N];
ll suf[N];
struct Node{
ll sum;
ll cnt;
};
struct SegTree{
Node T[M * 4 + 512];
void init(){
for(int i = 0 ;i < M * 4 + 512; i ++ )
T[i] = {0, 0};
}
void upd(int node, int cl, int cr, int pos, int v){
if(cl == cr){
T[node].sum += v;
T[node].cnt ++ ;
return;
}
int mid = (cl + cr) / 2;
if(mid >= pos)
upd(node * 2, cl, mid, pos, v);
else
upd(node * 2 + 1, mid + 1, cr, pos, v);
T[node].sum = T[node * 2].sum + T[node * 2 + 1].sum;
T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}
Node get(int node, int cl, int cr, int tl, int tr){
if(cr < tl || cl > tr)
return {0,0};
if(cl >= tl && cr <= tr){
return T[node];
}
int mid = (cl + cr) / 2;
Node lef = get(node * 2, cl, mid, tl, tr);
Node rig = get(node * 2 + 1, mid + 1, cr, tl, tr);
lef.sum += rig.sum;
lef.cnt += rig.cnt;
return lef;
}
};
SegTree up, down;
multiset<int> low, high;
int main(){
fastIO;
int k, n;
cin >> k >> n;
vector<pii> posi;
char a1, a2;
int f1, f2;
ll total = 0;
for(int i = 1; i <= n; i ++ ){
cin >> a1 >> f1 >> a2 >> f2;
if(a1 == a2){
total += abs(f2-f1);
}
else{
total ++ ;
if(a1 == 'B'){
swap(f1, f2);
}
posi.push_back(mp(f1, f2));
uni.push_back(f1);
uni.push_back(f2);
}
}
sort(uni.begin(), uni.end());
uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
sort(posi.begin(), posi.end());
int sz = uni.size();
int fe, fp;
int med;
ll dist;
for(int i = 0 ; i < posi.size(); i ++ ){
low.insert(posi[i].fi);
high.insert(posi[i].se);
while(1){
auto en = low.end();
en -- ;
auto pv = high.begin();
fe = *en;
fp = *pv;
if(fe > fp){
low.erase(en);
high.erase(pv);
low.insert(fp);
high.insert(fe);
}
else{
break;
}
}
up.upd(1, 0, sz - 1, id(posi[i].fi), posi[i].fi);
down.upd(1, 0, sz - 1, id(posi[i].se), posi[i].se);
auto it = low.end();
-- it;
med = *it;
dist = 0;
Node lf = up.get(1, 0, sz - 1, 0, id(med)-1);
Node rf = up.get(1, 0, sz - 1, id(med)+1, sz - 1);
dist += med * 1ll * lf.cnt - lf.sum;
dist += rf.sum - med * 1ll * rf.cnt;
lf = down.get(1, 0, sz - 1, 0, id(med)-1);
rf = down.get(1, 0, sz - 1, id(med)+1, sz - 1);
dist += med * 1ll * lf.cnt - lf.sum;
dist += rf.sum - med * 1ll * rf.cnt;
pf[i + 1] = dist;
}
up.init();
down.init();
low.clear();
high.clear();
for(int i = posi.size() - 1;i >= 0 ; i -- ){
low.insert(posi[i].fi);
high.insert(posi[i].se);
while(1){
auto en = low.end();
en -- ;
auto pv = high.begin();
fe = *en;
fp = *pv;
if(fe > fp){
low.erase(en);
high.erase(pv);
low.insert(fp);
high.insert(fe);
}
else{
break;
}
}
up.upd(1, 0, sz - 1, id(posi[i].fi), posi[i].fi);
down.upd(1, 0, sz - 1, id(posi[i].se), posi[i].se);
auto it = high.begin();
med = *it;
dist = 0;
Node lf = up.get(1, 0, sz - 1, 0, id(med)-1);
Node rf = up.get(1, 0, sz - 1, id(med)+1, sz - 1);
dist += med * 1ll * lf.cnt - lf.sum;
dist += rf.sum - med * 1ll * rf.cnt;
lf = down.get(1, 0, sz - 1, 0, id(med)-1);
rf = down.get(1, 0, sz - 1, id(med)+1, sz - 1);
dist += med * 1ll * lf.cnt - lf.sum;
dist += rf.sum - med * 1ll * rf.cnt;
suf[i + 1] = dist;
}
if(k == 1){
ll ans = (ll)1e14;
for(int k = posi.size(); k <= posi.size(); k ++ ){
vector<int> pps;
for(int i = 0 ; i < k ; i ++ ){
pps.push_back(posi[i].fi);
pps.push_back(posi[i].se);
}
sort(pps.begin(), pps.end());
int med = pps[(int)pps.size() / 2];
ll cur = 0;
for(int i = 0 ; i < k; i ++ ){
cur += abs(posi[i].fi - med) + abs(posi[i].se - med);
}
pps.clear();
for(int i = k; i < posi.size(); i ++ ){
pps.push_back(posi[i].fi);
pps.push_back(posi[i].se);
}
sort(pps.begin(), pps.end());
if(pps.size() > 0){
med = pps[(int)pps.size() / 2];
for(int i = k ; i < posi.size(); i ++ ){
cur += abs(posi[i].fi - med) + abs(posi[i].se - med);
}
}
cout << cur + total;
return 0;
}
cout << ans+total << "\n";
}
else{
ll ans = (ll)1e14;
for(int k = 1; k <= posi.size(); k ++ ){
vector<int> pps;
for(int i = 0 ; i < k ; i ++ ){
pps.push_back(posi[i].fi);
pps.push_back(posi[i].se);
}
sort(pps.begin(), pps.end());
int med = pps[(int)pps.size() / 2];
ll cur = 0;
for(int i = 0 ; i < k; i ++ ){
cur += abs(posi[i].fi - med) + abs(posi[i].se - med);
}
pps.clear();
for(int i = k; i < posi.size(); i ++ ){
pps.push_back(posi[i].fi);
pps.push_back(posi[i].se);
}
sort(pps.begin(), pps.end());
if(pps.size() > 0){
med = pps[(int)pps.size() / 2];
for(int i = k ; i < posi.size(); i ++ ){
cur += abs(posi[i].fi - med) + abs(posi[i].se - med);
}
}
ans=min(ans,cur);
}
cout << ans+total << "\n";
}
return 0;
}
