#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 1e18;
struct AIB
{
vector<int> aib;
int mar;
AIB (int marime)
{
mar = marime;
aib.resize(marime + 1);
}
void update(int pos,int val)
{
for (int i = pos; i <= mar; i += (i & -i))
aib[i] += val;
}
int query(int pos)
{
int rr = 0;
for (int i = pos; i > 0; i -= (i & -i))
rr += aib[i];
return rr;
}
};
int n,k;
char p[100005],q[100005];
int s[100005],t[100005];
int ans;
int real_value[200005];
int m;
void normalize()
{
set<int> vls;
for (int i = 1; i <= n; i++)
{
vls.insert(s[i]);
vls.insert(t[i]);
}
map<int,int> norma;
int itr = 0;
for (auto it : vls)
{
itr++;
norma[it] = itr;
real_value[itr] = it;
}
m = itr;
for (int i = 1; i <= n; i++)
s[i] = norma[s[i]],t[i] = norma[t[i]];
}
int y_opt[200005];
int f(int x,int y)
{
int dev = 0;
for (int i = 1; i <= n; i++)
{
if (t[i] < x)
dev += 2 * (real_value[x] - real_value[t[i]]);
else if (s[i] > y)
dev += 2 * (real_value[s[i]] - real_value[y]);
else if (s[i] > x and t[i] < y)
dev += 2 * min(real_value[s[i]] - real_value[x],real_value[y] - real_value[t[i]]);
}
return dev;
}
void solve(int l, int r, int st, int dr)
{
if (l > r)
return;
int mij = (l + r) / 2;
int bst = inf;
for (int i = st; i <= dr; i++)
{
int cat = f(mij,i);
if (cat < bst)
{
bst = cat;
y_opt[mij] = i;
}
}
solve(l,mij - 1,st,y_opt[mij]);
solve(mij + 1,r,y_opt[mij],dr);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i] >> s[i] >> q[i] >> t[i];
if (s[i] > t[i])
swap(s[i],t[i]);
ans += t[i] - s[i];
if (p[i] == q[i])
n--,i--;
}
ans += n;
if (n <= k)
{
cout << ans << '\n';
return 0;
}
normalize();
if (k == 1)
{
AIB aib_cnt_r(m), aib_sum_r(m), aib_cnt_l(m), aib_sum_l(m);
for (int i = 1; i <= n; i++)
{
aib_cnt_r.update(t[i],1);
aib_sum_r.update(t[i],real_value[t[i]]);
aib_cnt_l.update(s[i],1);
aib_sum_l.update(s[i],real_value[s[i]]);
}
int devmin = inf;
for (int i = 1; i <= m; i++)
{
int cr = aib_cnt_r.query(i - 1),sr = aib_sum_r.query(i - 1),cl = aib_cnt_l.query(m) - aib_cnt_l.query(i),sl = aib_sum_l.query(m) - aib_sum_l.query(i);
int x = real_value[i];
int dev = 2 * (x * cr - sr + sl - x * cl);
devmin = min(devmin,dev);
}
cout << ans + devmin;
}
else
{
solve(1,m,1,m);
int devmin = inf;
for (int i = 1; i <= m; i++)
devmin = min(devmin,f(i,y_opt[i]));
cout << ans + devmin;
}
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
/**
Obs: merita sa fac pod doar unde e cv cladire, adica in O(N) locatii
Initial adun abs(S[i] - T[i]) la toate, fac S[i] <= T[i], daca P[i] = Q[i] il elimin, altfel mai adaug 1 si presupun P[i] = A, Q[i] = B
N o sa fie cate intervale au P[i] != Q[i]
K = 1 -> fixez unde fac podul, vad cate au R in stanga si suma R-urilor, cate au L in dreapta si suma L-urilor, cv formula
K = 2
Fie x si y locatiile (dintre cele O(N)) in care imi fac podurile
Cred (doamne ajuta adica) ca daca imi fixez un x, y_opt(x) e crescator (divide dp stuff)
Hai sa zicem ca am eu o functie magica f(x,y) care imi calculeaza suma devierilor daca fac poduri in x si y
Pai f(x,y) functioneaza gen: ia toate alea cu R < x si zice cate si suma, toate cu L > y si zice cate si suma etc penal
Problema apare la alea x < L <= R < y ca am min(L - x, y - R)
Aici, zic asa: fie mij = x + y (omit / 2 ca nu conteaza) si m = L + R
Daca m <= mij, L - x e minim, altfel R - y e minim
Atunci f(x,y) zice: gaseste toti aia cu L > x si m <= mij si zi cati si suma L-urilor (oricum asta imi garanteaza y < R)
Apoi, gaseste toti aia cu R < y si m > mij si zi cati si suma R-urilor (once again, asta garanteaza L > x)
In functie de chestiile alea am o formula penala pentru f(x,y)
Daca ar intra aib-ul 2D (adica Nlog^3 complexitate) atunci doar pot face divide dp-ul simplu, aflu y_opt(x) si totul e bine
Schema e asa: Hai sa incerc, pentru toti y din [st, dr], sa gasesc f-ul mergand frumos prin ei
Prima parte e: cumva sa pun mana pe toti cu L > x, m <= mij
Hai sa imi tin in cv structura (peste care voi tine aib-urile) toti cu L > x
Pai, initial pun toti cu L > x (care inca nu au fost pusi) in structura
Calculez acum doar din aib-uri partea lor de f(x,y)
Pentru cei cu R < y, m > mij: Again, cum merg cu y crescator, bag in (alta) structura cei cu R == y - 1
Din structura aia dau query de suma si de cati pentru cei cu m > mij
Astfel, doar din operatii pe aib, am calculat y_opt(x)
Schema e asa: cand dau divide in bucata din stanga, trebuie sa am toti L > x_mij, pentru ca apoi sa pun doar cei care tin de x_left
Cand dau divide in bucata dreapta, trebuie sa am pusi in structura a doua pe toti cei cu y < y_opt(x_mij)
In felul asta, complexitatea ramane Nlog^2 (holy shit cum implementez eu toata asta)
Hai sa testez mai intai daca chiar merge divide dp-ul lol
**/
