#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;
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);
else MO(tree[i].r,mid+1,r,num,v);
}
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;
}
ll mid = (l+r)/2;
QU(tree[o].l, l,mid, L, R);
QU(tree[o].r,mid+1,r, L, R);
}
vector<int> lhistory, rhistory;
vector<int> lrev;
map<ll, int> segmp;
ll C(ll l, ll r) {
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;
re += (L+1) * (l) - (rps[L+1]);
int lat = lower_bound(ALL(lrev), l, greater<int>()) - lrev.begin() - 1;
int rat = lower_bound(ALL(rbs), r) - rbs.begin()-1;
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;
vector<int> smawk(vector<int> row, vector<int> col){
if (SZ(col) <= 4) {
vector<int> ret;
for (int i = 0; i<SZ(row); ++i){
ll mybest = 1e18+2;
ret.pb(0);
for (int j = 0; j<SZ(col); ++j) {
ll cc = C(row[i], col[j]);
if (cc < mybest) {
ret.back() = col[j];
mybest = cc;
}
}
RE=min(RE,mybest);
}
return ret;
}
if (SZ(col) > SZ(row)) {
vector<int> nc;
for (ll cc : col) {
while (true) {
if (nc.size() == 0) break;
ll rr = row[nc.size() - 1];
if (C(rr, cc) > C(rr, nc.back()))
break;
nc.pop_back();
}
if (nc.size() < row.size())
nc.push_back(cc);
}
return smawk(row, 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; k < SZ(col) && col[k] >= pos[i/2]; ++k) {
ll cc = C(row[i], col[k]);
if (cc < mybest) {
mybest = cc; ret.back() = col[k];
}
j=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) {
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];
}
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;
}
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);
bug(ele.f);
}
vector<int> c = r;
reverse(ALL(c));
reverse(ALL(r));
vector<int> lol = smawk(r,c);
for (int x : lol) bug(x);
bug(RE);
cout<<re + RE*2 + n<<endl;
}
}
