#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
using namespace std;
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif // BALBIT
//#define int ll
#define pii pair<ll, ll>
#define f first
#define s second
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x.size())
#define pb push_back
vector<pii> v;
int n;
const int maxn = 1e5+3;
vector<int> rbs, lbs;// right bounds and left bounds, separated and sorted
ll rps[maxn], lps[maxn];// right bounds and left bounds, separated and sorted and ps
struct node{
int l=0,r=0;
ll val=0;
int sz=0;
} tree [maxn<<6];
int T_cnt = 0;
//inline ll getval(node *&o){return o?o->val:0;}
//inline int getsz(node *&o){return o?o->sz:0;}
//
void build(int &o, int l, int r) {
o = T_cnt++;
if (l == r) {
return;
}
int mid = (l+r)/2;
build(tree[o].l,l,mid);
build(tree[o].r,mid+1,r);
}
inline void MO(int &i,int l,int r, ll num, ll v) //&的神奇功能，会把外面传入变量一起改变
{
tree[T_cnt++]=tree[i]; //先继承上一棵树的信息
i=T_cnt-1; //修改子树关系
++tree[i].sz;
tree[i].val += v;
if (l==r) return;
int mid=(l+r)>>1;
if (num<=mid) MO(tree[i].l,l,mid,num,v); //小于等于mid则在左边更新，右边直接与上一棵树共用
else MO(tree[i].r,mid+1,r,num,v); //大于mid，左边更新，右边共用
// tree[i].sz = tree[i].l.sz + tree[i].r.sz;
// tree[i].val = tree[i].l.val + tree[i].r.val;
}
ll A=0, B=0;
void QU(int o, int l, int r, int L, int R) {
if (l > R || r<L) return;
if (l>=L && r <=R) {
A += tree[o].val; B += tree[o].sz;
return;
// tree[o].val, tree[o].sz;
}
ll mid = (l+r)/2;
QU(tree[o].l, l,mid, L, R);
QU(tree[o].r,mid+1,r, L, R);
// return {A.f+B.f, A.s+B.s};
}
vector<int> lhistory, rhistory;
vector<int> lrev;
map<ll, int> segmp;
ll C(ll l, ll r) {
// if (l>r) return 10000000000000000ll;
int L = lower_bound(ALL(rbs), l) - rbs.begin() -1;// right bounds less than l
int R = upper_bound(ALL(lbs), r) - lbs.begin();// right bounds less than l
ll re = 0;
re += (lps[n] - lps[R]) - (n-R) * r;
// bug(re);
// bug(L+1);
re += (L+1) * (l) - (rps[L+1]);
// bug(re);
int lat = lower_bound(ALL(lrev), l, greater<int>()) - lrev.begin() - 1;
int rat = lower_bound(ALL(rbs), r) - rbs.begin()-1;
// bug(lat, rat);
auto sit = segmp.lower_bound(r+l);
A=B=0;
QU(lhistory[lat+1], 0, 1e5+3, 0, (*prev(sit)).s);
re += A - B * l;
A=B=0;
QU(rhistory[rat+1], 0, 1e5+3, (*(sit)).s, 1e5+3);
re += B*r-A;
return re;
}
ll RE;
vector<int> p;
int m;
// node * lroot = 0, *rroot = 0;
vector<int> smawk(vector<int> row, vector<int> col){
bug("SMAWK!", SZ(row), SZ(col));
if (SZ(col) <= 2) {
vector<int> ret;
for (int i = 0; i<SZ(row); ++i){
ll mybest = 1e18+2;
ret.pb(-1);
for (int j = 0; j<SZ(col); ++j) {
ll cc = C(row[i], col[j]);
if (cc < mybest) {
ret.back() = j;
mybest = cc;
}
}
RE=min(RE,mybest);
}
return ret;
}
if (SZ(col) > SZ(row)) {
// Reduce!
int i = 0;
vector<int> nr;
vector<int> nc;
for (int j = 0; i<SZ(row) && j<SZ(col); ++j) {
// Can be optimized
bug(i,j);
if (j == SZ(col)-1 || C(row[i], col[j]) < C(row[i], col[j+1])) {
nr.pb(row[i]);
nc.pb(col[j]);
++i;
}
}
return smawk(nr, nc);
}else{
vector<int> odds;
for (int i = 1; i<SZ(row); i += 2) {
odds.pb(row[i]);
}
vector<int> pos = smawk(odds, col);
pos.pb(col.back());
vector<int> ret;
int j = 0;
for (int i = 0; i<SZ(row); i++) {
if (i & 1) {
ret.pb(pos[i/2]);
}else{
ret.pb(col[j]);
ll mybest = 1e18+2;
for (int k = j; col[k] <= pos[i/2+1]; ++k) {
ll cc = C(row[i], col[k]);
if (cc < mybest) {
mybest = cc; ret.back() = col[k];
}
}
RE = min(RE, mybest);
}
}
return ret;
}
}
signed main(){
IOS();
int k; cin>>k>>n;
ll re = 0;
map<int, int> hv;
for (int i = 0; i<n; ++i) {
char x, x2;
int l, r; cin>>x>>l>>x2>>r;
re += abs(r-l);
if (x == x2) {
}else{
if (r < l) swap(l,r);
v.pb({l,r});
rbs.pb(r);
lbs.pb(l);
hv[l]--;
hv[r]--;
}
}
n = SZ(v);
lhistory.pb(0); rhistory.pb(0);
sort(ALL(v), [&](pii a, pii b){return a.f>b.f;});
vector<ll> fff;
for (int i = 0; i<n; ++i) {
fff.pb(v[i].f + v[i].s);
}
sort(ALL(fff));
for (int i = 0; i<n; ++i) {
segmp[fff[i]] = i;
}
segmp[-1]=-1;
build(lhistory.back(), 0, 1e5+3);
for (int i = 0; i<n; ++i) {
int topb = T_cnt;
int tmp = lhistory.back();
MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].f);
lhistory.pb(topb);
}
sort(ALL(v), [&](pii a, pii b){return a.s<b.s;});
build(rhistory.back(), 0, 1e5+3);
bug(rhistory.back());
for (int i = 0; i<n; ++i) {
// if (v[i].s == 6) bug(v[i].s, v[i].f+v[i].s);
int topb = T_cnt;
int tmp = rhistory.back();
MO(tmp, 0, 1e5+3, segmp[v[i].f+v[i].s], v[i].s);
rhistory.pb(topb);
}
bug(rhistory.back());
sort(ALL(rbs));
sort(ALL(lbs));
lrev = lbs;
sort(ALL(lrev), greater<int>());
for (int i = 0; i<n; ++i) {
rps[i+1] = rps[i] + rbs[i];
lps[i+1] = lps[i] + lbs[i];
}
// int L, R;
// while (cin>>L>>R) {
// cout<<C(L, R)<<endl;
// }
//
// return 0;
if (k == 1) {
ll now = lps[n];
bug(now);
ll ans = now;
ll x = 0;
ll frt = n;
for (pii ele : hv) {
ll X = ele.f;
now -= (X-x) * (frt);
bug(X, now);
ans = min(ans, now);
frt += ele.s;
x=X;
}
// if (ans == 1000000000000000ll) ans = 0;
cout<<re + ans*2 + n<<endl;
}else{
m = SZ(hv);
p.resize(m);
RE = C(0,0);
int _it = 0;
vector<int> r;
for (pii ele : hv) {
p[_it++] = ele.f;
r.pb(ele.f);
}
vector<int> c = r;
reverse(ALL(c));
smawk(r,c);
// cout<<re + ans*2 + n<<endl;
bug(RE);
cout<<re + RE*2 + n<<endl;
#ifdef BALBIT
for (int i = 0; i<SZ(r); ++i) {
for (int j = 0; j<SZ(c); ++j) {
cout<<C(r[i],c[j])<<' ';
}
cout<<endl;
}
#endif
}
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
