#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(), A.end()
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)b; i--)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define se second
const int oo = (int) 2e9;
const long long INF = (long long) 1e18;
const int MAXN = (int) 4e5 + 5;
int K, N;
char P[MAXN], Q[MAXN];
int S[MAXN], T[MAXN];
namespace sub1 {
int A[MAXN];
int M;
long long res = 0;
long long pre[MAXN];
void solve() {
FOR(i, 1, N) {
if (P[i] != Q[i]) {
A[++ M] = S[i];
A[++ M] = T[i];
} else res+= abs(S[i] - T[i]);
}
N = M;
sort(A + 1, A + 1 + N);
FOR(i, 1, N) pre[i] = pre[i - 1] + A[i];
long long ans = (N > 0 ? INF : 0);
FOR(i, 1, N) {
int x = A[i];
long long sum = 1LL * i * x - pre[i] - 1LL * (N - i + 1) * x + pre[N] - pre[i - 1];
ans = min(ans, sum);
}
cout << res + ans + N / 2;
}
}
namespace sub2 {
int A[MAXN];
int M;
long long res = 0;
void solve() {
vector <int> Place;
FOR(i, 1, N) {
if (P[i] == Q[i]) res+= abs(S[i] - T[i]);
else {
Place.push_back(S[i]);
Place.push_back(T[i]);
}
}
sort(ALL(Place));
long long ans = (Place.size() > 1 ? INF : 0);
FOR(i, 0, Place.size() - 1) {
int x1 = Place[i];
FOR(j, i + 1, Place.size() - 1) {
int x2 = Place[j];
long long sum = 0;
FOR(t, 1, N) if (P[t] != Q[t]) {
sum+= min(abs(S[t] - x1) + abs(T[t] - x1), abs(S[t] - x2) + abs(T[t] - x2)) + 1;
}
ans = min(ans, sum);
}
}
cout << ans + res;
}
}
namespace sub3 {
vector <pair <int, int>> Line;
long long res = 0;
long long L[MAXN], R[MAXN];
void solve() {
FOR(i, 1, N) {
if (P[i] != Q[i]) {
if (S[i] > T[i]) swap(S[i], T[i]);
Line.push_back(make_pair(S[i], T[i]));
} else res+= abs(S[i] - T[i]);
}
sort(ALL(Line), [&](pair <int, int> u, pair <int, int> v) {
return u.fi + u.se < v.fi + v.se;
});
N = Line.size() - 1;
/// calc For Left
vector <int> Point;
FOR(i, 0, N) {
Point.push_back(Line[i].fi);
Point.push_back(Line[i].se);
sort(ALL(Point));
int x = Point[(Point.size() + 1) / 2];
long long sum = 0;
for (const int &xxx : Point) sum+= abs(xxx - x);
L[i] = sum;
}
Point.clear();
/// calc For Right
FORD(i, N, 0) {
Point.push_back(Line[i].fi);
Point.push_back(Line[i].se);
sort(ALL(Point));
int x = Point[(Point.size() + 1) / 2];
long long sum = 0;
for (const int &xxx : Point) sum+= abs(xxx - x);
R[i] = sum;
}
long long ans = (N > 0 ? INF : 0);
FOR(i, 0, N - 1) {
ans = min(ans, L[i] + R[i + 1]);
}
cout << ans + res + N + 1;
}
}
namespace sub4 {
int deCompress[MAXN];
vector <pair <int, int>> Line;
long long res = 0;
int VAL;
long long L[MAXN], R[MAXN];
void Compress(void) {
vector <int> X;
FOR(i, 0, N) {
X.push_back(Line[i].fi);
X.push_back(Line[i].se);
}
sort(ALL(X)); X.resize(unique(ALL(X)) - X.begin());
FOR(i, 0, N) {
int p_X = upper_bound(ALL(X), Line[i].fi) - X.begin();
deCompress[p_X] = Line[i].fi, Line[i].fi = p_X;
int p_Y = upper_bound(ALL(X), Line[i].se) - X.begin();
deCompress[p_Y] = Line[i].se, Line[i].se = p_Y;
}
VAL = X.size();
}
struct FenwickTree {
long long bit[MAXN];
inline void update(int u, int val) {
for (int i = u; i <= VAL; i+=i&-i) bit[i]+= val;
}
inline long long get(int u) {
long long sum = 0;
for (int i = u; i; i-=i&-i) sum+= bit[i];
return sum;
}
inline long long get(int l, int r) {
return get(r) - get(l - 1);
}
void clear() {
memset(bit, 0, sizeof bit);
}
} fwtSum, fwtCnt;
void calcLeft(void) {
fwtSum.clear();
fwtCnt.clear();
FOR(i, 0, N - 1) {
fwtCnt.update(Line[i].fi, 1); fwtCnt.update(Line[i].se, 1);
fwtSum.update(Line[i].fi, deCompress[Line[i].fi]); fwtSum.update(Line[i].se, deCompress[Line[i].se]);
int median = 0, l = 1, r = VAL;
while (l <= r) {
int mid = (l + r) >> 1;
if (fwtCnt.get(mid) > i) median = mid, r = mid - 1;
else l = mid + 1;
}
long long sumLeft = 1LL * deCompress[median] * fwtCnt.get(median) - fwtSum.get(median);
long long sumRight = fwtSum.get(median, VAL) - 1LL * deCompress[median] * fwtCnt.get(median, VAL);
L[i] = sumLeft + sumRight;
}
}
void calcRight(void) {
fwtSum.clear();
fwtCnt.clear();
int cnt = 0;
FORD(i, N, 0) {
cnt++;
fwtCnt.update(Line[i].fi, 1); fwtCnt.update(Line[i].se, 1);
fwtSum.update(Line[i].fi, deCompress[Line[i].fi]); fwtSum.update(Line[i].se, deCompress[Line[i].se]);
int median = 0, l = 1, r = VAL;
while (l <= r) {
int mid = (l + r) >> 1;
if (fwtCnt.get(mid) >= cnt) median = mid, r = mid - 1;
else l = mid + 1;
}
long long sumLeft = 1LL * deCompress[median] * fwtCnt.get(median) - fwtSum.get(median);
long long sumRight = fwtSum.get(median, VAL) - 1LL * deCompress[median] * fwtCnt.get(median, VAL);
R[i] = sumLeft + sumRight;
}
}
void solve() {
FOR(i, 1, N) {
if (P[i] != Q[i]) {
if (S[i] > T[i]) swap(S[i], T[i]);
Line.push_back(make_pair(S[i], T[i]));
} else res+= abs(S[i] - T[i]);
}
sort(ALL(Line), [&](pair <int, int> u, pair <int, int> v) {
return u.fi + u.se < v.fi + v.se;
});
N = Line.size() - 1;
Compress();
calcLeft(); calcRight();
long long ans = (N > 0 ? INF : 0);
FOR(i, 0, N - 1) ans = min(ans, L[i] + R[i + 1]);
cout << ans + res + N + 1;
}
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define Hori ""
if (fopen(Hori".inp", "r")) {
freopen(Hori".inp", "r", stdin);
freopen(Hori".out", "w", stdout);
}
cin >> K >> N;
for (int i = 1; i <= N; i++) cin >> P[i] >> S[i] >> Q[i] >> T[i];
if (K == 1) return sub1 :: solve(), 0;
return sub4 :: solve(), 0;
return void(cerr << "KO :" << TIME << "s "), (0 ^ 0);
}
