#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll inf = (ll)1e9 * (ll)1e9;
int tuf = (int)2e9 + 1;
const int NN = 6200000;
int n,k;
char p[100005],q[100005];
int s[100005],t[100005];
ll ans;
ll real_value[200005];
int m;
ll cate_r[200005],sum_r[200005],cate_l[200005],sum_l[200005];
map<int,int> huh;
vector<int> vvv;
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]];
set<int> vls2;
for (int i = 1; i <= n; i++)
vls2.insert(real_value[s[i]] + real_value[t[i]]);
itr = 0;
for (auto it : vls2)
{
itr++;
huh[it] = itr;
vvv.push_back(it);
}
}
int down_lpr(int x)
{
if (x < vvv[0])
return 0;
int st = 0,pas = 1 << 16;
while (pas != 0)
{
if (st + pas < vvv.size() and vvv[st + pas] <= x)
st += pas;
pas /= 2;
}
return st + 1;
}
int up_lpr(int x)
{
if (x > vvv.back())
return 0;
int st = -1,pas = 1 << 16;
while (pas != 0)
{
if (st + pas < vvv.size() and vvv[st + pas] < x)
st += pas;
pas /= 2;
}
return st + 2;
}
int y_opt[200005];
pair<int,ll> aint[NN + 5];
int fs[NN + 5],fd[NN + 5];
int roots1[200005],roots2[200005];
int cate;
pair<int,ll> query(int nod, int l, int r, int st, int dr)
{
if (aint[nod].first == 0)
return {0,0};
if (r < st or dr < l)
return {0,0};
if (st <= l and r <= dr)
return aint[nod];
int mij = (ll)((ll)l + (ll)r) / 2;
pair<int,ll> p1 = query(fs[nod],l,mij,st,dr),p2 = query(fd[nod],mij + 1,r,st,dr);
return {p1.first + p2.first,p1.second + p2.second};
}
void update(int nod, int l, int r, int pos, int val)
{
if (l == r)
{
aint[nod].first++;
aint[nod].second += val;
}
else
{
int mij = (ll)((ll)l + (ll)r) / 2;
if (pos <= mij)
{
cate++;
aint[cate] = aint[fs[nod]];
fs[cate] = fs[fs[nod]];
fd[cate] = fd[fs[nod]];
fs[nod] = cate;
update(fs[nod],l,mij,pos,val);
}
else
{
cate++;
aint[cate] = aint[fd[nod]];
fs[cate] = fs[fd[nod]];
fd[cate] = fd[fd[nod]];
fd[nod] = cate;
update(fd[nod],mij + 1,r,pos,val);
}
aint[nod] = {aint[fs[nod]].first + aint[fd[nod]].first,aint[fs[nod]].second + aint[fd[nod]].second};
}
}
ll f(int x,int y)
{
ll dev = 0;
dev += real_value[x] * cate_r[x - 1] - sum_r[x - 1];
dev += sum_l[y + 1] - real_value[y] * cate_l[y + 1];
int cn = down_lpr(real_value[x] + real_value[y]);
pair<int,ll> p1;
if (cn == 0)
p1 = {0,0};
else
p1 = query(roots1[x],1,n,1,cn);///.first = cate, .second = suma L-urilor reale
cn = up_lpr(real_value[x] + real_value[y] + 1);
pair<int,ll> p2;
if (cn == 0)
p2 = {0,0};
else
p2 = query(roots2[y],1,n,cn,n);///.first = cate, .second = suma R-urilor reale
dev += p1.second - p1.first * real_value[x];
dev += p2.first * real_value[y] - p2.second;
dev *= 2;
return dev;
}
void solve(int l, int r, int st, int dr)
{
if (l > r)
return;
int mij = (l + r) / 2;
ll bst = inf;
for (int i = st; i <= dr; i++)
{
ll 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);
}
vector<pair<int,int>> cine_r[200005],cine_l[200005];
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();
//for (int i = 1; i <= n; i++)
// cout << s[i] << ' ' << t[i] << endl;
for (int i = 1; i <= n; i++)
{
cine_l[s[i]].push_back({s[i],t[i]});
cine_r[t[i]].push_back({s[i],t[i]});
}
for (int i = 1; i <= n; i++)
{
cate_r[t[i]]++;
sum_r[t[i]] += real_value[t[i]];
cate_l[s[i]]++;
sum_l[s[i]] += real_value[s[i]];
}
for (int i = 1; i <= m; i++)
{
cate_r[i] += cate_r[i - 1];
sum_r[i] += sum_r[i - 1];
}
for (int i = m; i >= 1; i--)
{
cate_l[i] += cate_l[i + 1];
sum_l[i] += sum_l[i + 1];
}
if (k == 1)
{
ll devmin = inf;
for (int i = 1; i <= m; i++)
{
ll cr = cate_r[i - 1],sr = sum_r[i - 1],cl = cate_l[i + 1],sl = sum_l[i + 1];
//cout << cr << ' ' << sr << ' ' << cl << ' ' << sl << endl;
ll x = real_value[i];
ll dev = 2 * (x * cr - sr + sl - x * cl);
devmin = min(devmin,dev);
}
cout << ans + devmin;
}
else
{
cate = 2 * m;
for (int i = 1; i <= m; i++)
roots1[i] = i;
for (int i = 1; i <= m; i++)
roots2[i] = i + m;
for (int x = m; x >= 1; x--)
{
aint[x] = aint[x + 1];
fs[x] = fs[x + 1];
fd[x] = fd[x + 1];
for (auto interval : cine_l[x + 1])
update(x,1,n,huh[real_value[interval.first] + real_value[interval.second]],real_value[interval.first]);
}
for (int y = m + 1; y <= 2 * m; y++)
{
if (y != m + 1)
{
aint[y] = aint[y - 1];
fs[y] = fs[y - 1];
fd[y] = fd[y - 1];
}
for (auto interval : cine_r[y - m - 1])
update(y,1,n,huh[real_value[interval.first] + real_value[interval.second]],real_value[interval.second]);
}
solve(1,m,1,m);
ll devmin = inf;
for (int i = 1; i <= m; i++)
devmin = min(devmin,f(i,y_opt[i]));
cout << ans + devmin;
}
return 0;
}
/*
2 5
A 0 B 2
A 6 B 8
A 11 B 13
A 9 B 15
A 13 B 19
*/
/**
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 = r[x] + r[y] (omit / 2 ca nu conteaza) si m = r[L] + r[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)
Pai nu am update-uri sau ceva, deci pot sa ma uit asa:
- pentru alea cu R < x, doar imi tin ceva cate_r[x] si sum_r[x] (cate r < x si suma valorilor lor reale)
- pentru alea cu L > y, ceva analog pe sufixe
- pentru cate L > x si m <= mij, dat fiind ca nu am update-uri pot sa ma uit in versiunea x si sa intreb chestii pe m <= mij
Adica sa imi tin un aint persistent in care merg cu x de la m la 1 si imi tin pentru fiecare, structura pe alea cu L mai mare
-pentru R < y, m > mij, tot asa, un aint persistent de merg cu y de la 1 la m si tin strucura pe m cu alea cu R < y
Astfel, am o precalculare O(NlogN) timp si memorie si O(logN) timp pe query, deci Nlog^2 total
Hai ca mai stie cineva sa implementeze aint persistent
**/
