# include <bits/stdc++.h>
# define f first
# define s second
using namespace std;
const int N = 1e5 + 2;
struct st{
int cnt, l, r;
long long sum = 0;
st(){
cnt = sum = l = r = 0;
}
}t[2][N * 15];
int n, k, cn, sz = 1, flag;
long long ans = 1e18, p1[N], s1[N], p2[N], s2[N], ss;
vector <int> v, v1, v2;
pair < pair <int, int> , pair <char, char> > a[N];
pair <int, pair <int, int> > b[N];
void update(int type, int pos, int bl, int v = 1, int tl = 0, int tr = 1e9){
if(tl == tr){
if(bl > 0)
t[type][v].sum += tl, t[type][v].cnt ++;
else
t[type][v].sum -= tl, t[type][v].cnt --;
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm){
if(!t[type][v].l) t[type][v].l = ++ sz;
update(type, pos, bl, t[type][v].l, tl, tm);
}
else{
if(!t[type][v].r) t[type][v].r = ++ sz;
update(type, pos, bl, t[type][v].r, tm + 1, tr);
}
t[type][v].sum = t[type][t[type][v].l].sum + t[type][t[type][v].r].sum;
t[type][v].cnt = t[type][t[type][v].l].cnt + t[type][t[type][v].r].cnt;
}
}
long long get(int type, int cs, int l, int r, int v = 1, int tl = 0, int tr = 1e9){
if(l > tr || tl > r || !t[type][v].cnt || l > r) return 0;
if(l <= tl && tr <= r){
if(cs)
return t[type][v].cnt;
else{
return t[type][v].sum;
}
}
int tm = (tl + tr) >> 1;
return get(type, cs, l, r, t[type][v].l, tl, tm) +
get(type, cs, l, r, t[type][v].r, tm + 1, tr);
}
int main(){
cin >> k >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i].s.f >> a[i].f.f >> a[i].s.s >> a[i].f.s;
if(a[i].f.f > a[i].f.s) swap(a[i].f.f, a[i].f.s);
if(a[i].s.f != a[i].s.s) {
cn ++;
v1.push_back(a[i].f.f), v2.push_back(a[i].f.s);
b[cn] = {(a[i].f.f + a[i].f.s + 1), {a[i].f.f, a[i].f.s}};
} else {
ss += abs(a[i].f.s - a[i].f.f);
}
v.push_back(a[i].f.f);
v.push_back(a[i].f.s);
}
v1.push_back(-1e9);
v2.push_back(-1e9);
sort(b + 1, b + cn + 1);
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
for(int i = 1; i <= cn; i ++){
p1[i] = p1[i - 1] + v1[i];
p2[i] = p2[i - 1] + v2[i];
}
for(int i = cn; i >= 1; i --){
s1[i] = s1[i + 1] + v1[i];
s2[i] = s2[i + 1] + v2[i];
}
int pos = 0, ps = 0;
for(int i = 0; i < v.size(); i ++){
long long res = 0;
int x = v[i];
while(pos + 1 <= cn && v1[pos + 1] <= x) pos ++;
while(ps + 1 <= cn && v2[ps + 1] <= x) ps ++;
res += x * 1ll * pos - p1[pos];
res += x * 1ll * ps - p2[ps];
res += s1[pos + 1] - x * 1ll * (cn - pos);
res += s2[ps + 1] - x * 1ll * (cn - ps);
ans = min(ans, res + cn + ss);
}
if(k == 2){
for(int i = 0; i < v.size(); i ++){
ps = 0;
for(int j = 1; j <= cn; j ++){
update(1, b[j].s.f, 1);
update(1, b[j].s.s, 1);
}
for(int j = i + 1; j < v.size(); j ++){
long long res = 0;
int x = (v[i] + v[j] + 1);
while(b[ps + 1].f <= x && ps + 1 <= cn) {
ps ++;
update(0, b[ps].s.f, 1);
update(0, b[ps].s.s, 1);
update(1, b[ps].s.f, 0);
update(1, b[ps].s.s, 0);
}
res += v[i] * 1ll * get( 0, 1, 0, v[i]) - get( 0, 0, 0, v[i]);
res += get( 0, 0, v[i] + 1, 1e9) - v[i] * 1ll * get( 0, 1, v[i] + 1, 1e9);
res += v[j] * 1ll * get( 1, 1, 0, v[j]) - get( 1, 0, 0, v[j]);
res += get( 1, 0, v[j] + 1, 1e9) - v[j] * 1ll * get( 1, 1, v[j] + 1, 1e9);
res += ss + cn;
// if(res == 21){
// cout << v[i] * 1ll * get(0, 1, 0, v[i]) << " " << get(0, 0, 0, v[i]) << endl;
// cout << get(0, 0, v[i] + 1, 1e9) << " " << v[i] * get(0, 1, v[i] + 1, 1e9) << endl;
// cout << get(1, 1, 0, v[j]) << " " << get(1, 0, 0, v[j]) << endl;
// cout << get(1, 0, v[j] + 1, 1e9) << " " << v[j] * get(1, 1, v[j] + 1, 1e9) << endl;
// cout << v[i] << " " << v[j] << endl;
// return 0;
// }
ans = min(ans, res);
}
for(int j = 1; j <= ps; j ++){
update(0, b[j].s.f, 0);
update(0, b[j].s.s, 0);
}
for(int j = ps + 1; j <= cn; j ++){
update(1, b[j].s.f, 0);
update(1, b[j].s.s, 0);
}
}
}
cout << ans << endl;
}
/***
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
***/
