#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll,ll> pi;
ll maks = 0 ,mins= 1000000010 ;
#define fi first
#define sc second
#define mp make_pair
#define pb push_back
vector< pi> pasangan;
vector< ll> dict;
ll n;
ll independent = 0 ;
string a,b;
ll k;
ll x,y;
ll si;
ll ternary3( ll x) {
ll ret = 0 ;
for ( ll i= 0 ; i< si; i++ ) ret+ = labs ( pasangan[ i] .fi - x) + labs ( pasangan[ i] .sc - x) ;
return ret;
}
ll ternary2( ll x, ll y) {
ll ret = 0 ;
for ( ll i= 0 ; i< si; i++ ) {
ret+ = min( labs ( pasangan[ i] .fi - x) + labs ( pasangan[ i] .sc - x) ,labs ( pasangan[ i] .fi - y) + labs ( pasangan[ i] .sc - y) ) ;
}
return ret;
}
ll ternary1( ll x) {
ll l = 0 ,r= dict.size ( ) - 1 ;
while ( l< r) {
if ( l+ 10 >= r) {
ll i = l, j = r;
ll now = LONG_LONG_MAX;
ll ret;
for ( ll k= i; k<= j; k++ ) {
ll sek = ternary2( x,dict[ k] ) ;
if ( sek< now) {
now= sek;
ret= k;
}
}
l= r= ret;
}
ll lt = l+ ( r- l) / 3 ;
ll rt = l+ ( r- l) * 2 / 3 ;
if ( ternary2( x,dict[ lt] ) > ternary2( x,dict[ rt] ) ) l= lt;
else r = rt;
}
ll kel = ternary2( x,dict[ l] ) , ker = ternary2( x,dict[ r] ) ;
return min( kel,ker) ;
}
int main( ) {
ios_base:: sync_with_stdio ( false ) ;
cin >> k>> n;
while ( n-- ) {
cin >> a >> x >> b >> y;
dict.pb ( x) ; dict.pb ( y) ;
maks= max( maks,max( x,y) ) ;
mins= min( mins,min( x,y) ) ;
if ( a== b) independent + = labs ( x- y) ;
else {
pasangan.pb ( mp( x,y) ) ;
}
}
sort( dict.begin ( ) ,dict.end ( ) ) ;
si = pasangan.size ( ) ;
ll l = 0 , r = dict.size ( ) - 1 ;
if ( k== 1 ) {
while ( l< r) {
if ( l+ 10 >= r) {
ll i = l, j= r;
ll now = LONG_LONG_MAX;
ll ap;
for ( ll k= i; k<= j; k++ ) {
ll sek = ternary3( dict[ k] ) ;
if ( sek< now) {
now= sek;
ap= k;
}
}
l= r= ap;
}
ll lt = l+ ( r- l) / 3 ;
ll rt = l+ ( r- l) * 2 / 3 ;
if ( ternary3( dict[ lt] ) > ternary3( dict[ rt] ) ) l= lt;
else r= rt;
}
independent+ = si;
cout << independent+ min( ternary3( dict[ l] ) ,ternary3( dict[ r] ) ) << "\n " ;
return 0 ;
}
while ( l< r) {
if ( l+ 10 >= r) {
ll i = l, j= r;
ll now = LONG_LONG_MAX;
ll ap;
for ( ll k= i; k<= j; k++ ) {
ll sek = ternary1( dict[ k] ) ;
if ( sek< now) {
now= sek;
ap= k;
}
}
l= r= ap;
}
ll lt = l+ ( r- l) / 3 ;
ll rt = l+ ( r- l) * 2 / 3 ;
if ( ternary1( dict[ lt] ) > ternary1( dict[ rt] ) ) l= lt;
else r= rt;
}
independent+ = si;
cout << independent+ min( ternary1( dict[ l] ) ,ternary1( dict[ r] ) ) << "\n " ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8bGwsbGw+IHBpOwogbGwgbWFrcyA9IDAsbWlucz0xMDAwMDAwMDEwOwoKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNjIHNlY29uZAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawoKdmVjdG9yPHBpPiBwYXNhbmdhbjsKdmVjdG9yPGxsPiBkaWN0OwoKbGwgbjsKbGwgaW5kZXBlbmRlbnQgPSAwOwpzdHJpbmcgYSxiOwpsbCBrOwpsbCB4LHk7CmxsIHNpOwoKbGwgdGVybmFyeTMobGwgeCl7CglsbCByZXQgPSAwOwoJZm9yKGxsIGk9MDtpPHNpO2krKykgcmV0Kz1sYWJzKHBhc2FuZ2FuW2ldLmZpLXgpK2xhYnMocGFzYW5nYW5baV0uc2MteCk7CglyZXR1cm4gcmV0Owp9CgpsbCB0ZXJuYXJ5MihsbCB4LCBsbCB5KXsKCWxsIHJldCA9MDsKCWZvcihsbCBpPTA7aTxzaTtpKyspewoJCXJldCs9bWluKGxhYnMocGFzYW5nYW5baV0uZmkteCkrbGFicyhwYXNhbmdhbltpXS5zYy14KSxsYWJzKHBhc2FuZ2FuW2ldLmZpLXkpK2xhYnMocGFzYW5nYW5baV0uc2MteSkpOwoJfQoJcmV0dXJuIHJldDsKfQoKbGwgdGVybmFyeTEobGwgeCl7CglsbCBsID0gMCxyPWRpY3Quc2l6ZSgpLTE7Cgl3aGlsZShsPHIpewoJCWlmIChsKzEwPj1yKXsKCQkJbGwgaSA9IGwsIGogPSByOwoJCQlsbCBub3cgPUxPTkdfTE9OR19NQVg7CgkJCWxsIHJldDsKCQkJZm9yKGxsIGs9aTtrPD1qO2srKyl7CgkJCQlsbCBzZWsgPSB0ZXJuYXJ5Mih4LGRpY3Rba10pOwoJCQkJaWYgKHNlazxub3cpewoJCQkJCW5vdz1zZWs7CgkJCQkJcmV0PWs7CgkJCQl9CgkJCX0KCQkJbD1yPXJldDsKCQl9CgoJCWxsIGx0ID0gbCsoci1sKS8zOwoJCWxsIHJ0ID0gbCsoci1sKSoyLzM7CgoJCWlmICh0ZXJuYXJ5Mih4LGRpY3RbbHRdKT50ZXJuYXJ5Mih4LGRpY3RbcnRdKSkgbD1sdDsKCQllbHNlIHIgPSBydDsKCX0KCWxsIGtlbCA9IHRlcm5hcnkyKHgsZGljdFtsXSksIGtlciA9IHRlcm5hcnkyKHgsZGljdFtyXSk7CglyZXR1cm4gbWluKGtlbCxrZXIpOwp9CgppbnQgbWFpbigpewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4+Pms+Pm47Cgl3aGlsZShuLS0pewoJCWNpbiA+PiBhID4+IHggPj4gYiA+PiB5OwoJCWRpY3QucGIoeCk7IGRpY3QucGIoeSk7CgkJbWFrcz1tYXgobWFrcyxtYXgoeCx5KSk7CgkJbWlucz1taW4obWlucyxtaW4oeCx5KSk7CgkJaWYgKGE9PWIpIGluZGVwZW5kZW50ICs9IGxhYnMoeC15KTsKCQllbHNlewoJCQlwYXNhbmdhbi5wYihtcCh4LHkpKTsKCQl9Cgl9CgoJc29ydChkaWN0LmJlZ2luKCksZGljdC5lbmQoKSk7CglzaSA9IHBhc2FuZ2FuLnNpemUoKTsKCWxsIGwgPSAwLCByID0gZGljdC5zaXplKCktMTsKCQoJaWYgKGs9PTEpewoJCXdoaWxlKGw8cil7CgkJCWlmIChsKzEwPj1yKXsKCQkJCWxsIGkgPSBsLCBqPXI7CgkJCQlsbCBub3cgPSBMT05HX0xPTkdfTUFYOwoJCQkJbGwgYXA7CgkJCQlmb3IgKGxsIGs9aTtrPD1qO2srKyl7CgkJCQkJbGwgc2VrID0gdGVybmFyeTMoZGljdFtrXSk7CgkJCQkJaWYgKHNlazxub3cpewoJCQkJCQlub3c9c2VrOwoJCQkJCQlhcD1rOwoJCQkJCX0KCQkJCX0KCQkJCWw9cj1hcDsKCQkJfQoJCQlsbCBsdCA9IGwrKHItbCkvMzsKCQkJbGwgcnQgPSBsKyAoci1sKSoyLzM7CgoJCQlpZiAodGVybmFyeTMoZGljdFtsdF0pPnRlcm5hcnkzKGRpY3RbcnRdKSkgbD1sdDsKCQkJZWxzZSByPXJ0OwoJCX0KCgkJaW5kZXBlbmRlbnQrPXNpOwoJCWNvdXQgPDwgaW5kZXBlbmRlbnQrbWluKHRlcm5hcnkzKGRpY3RbbF0pLHRlcm5hcnkzKGRpY3Rbcl0pKSA8PCAiXG4iOwoJCXJldHVybiAwOwoJfQoKCXdoaWxlKGw8cil7CgkJaWYgKGwrMTA+PXIpewoJCQlsbCBpID0gbCwgaj1yOwoJCQlsbCBub3cgPSBMT05HX0xPTkdfTUFYOwoJCQlsbCBhcDsKCQkJZm9yIChsbCBrPWk7azw9ajtrKyspewoJCQkJbGwgc2VrID0gdGVybmFyeTEoZGljdFtrXSk7CgkJCQlpZiAoc2VrPG5vdyl7CgkJCQkJbm93PXNlazsKCQkJCQlhcD1rOwoJCQkJfQoJCQl9CgkJCWw9cj1hcDsKCQl9CgkJbGwgbHQgPSBsKyhyLWwpLzM7CgkJbGwgcnQgPSBsKyAoci1sKSoyLzM7CgoJCWlmICh0ZXJuYXJ5MShkaWN0W2x0XSk+dGVybmFyeTEoZGljdFtydF0pKSBsPWx0OwoJCWVsc2Ugcj1ydDsKCX0KCglpbmRlcGVuZGVudCs9c2k7Cgljb3V0IDw8IGluZGVwZW5kZW50K21pbih0ZXJuYXJ5MShkaWN0W2xdKSx0ZXJuYXJ5MShkaWN0W3JdKSkgPDwgIlxuIjsKfQ==
stdin
MiAyMApBIDAgQiAxMDAwMDAwMDAwCkEgMSBCIDk5OTk5OTk5OQpBIDIgQiA5OTk5OTk5OTgKQSAzIEIgOTk5OTk5OTk3CkEgNCBCIDk5OTk5OTk5NgpBIDUgQiA5OTk5OTk5OTUKQSA2IEIgOTk5OTk5OTk0CkEgNyBCIDk5OTk5OTk5MwpBIDggQiA5OTk5OTk5OTIKQSA5IEIgOTk5OTk5OTkxCkEgMTAgQiA5OTk5OTk5OTAKQSAxMSBCIDk5OTk5OTk4OQpBIDEyIEIgOTk5OTk5OTg4CkEgMTMgQiA5OTk5OTk5ODcKQSAxNCBCIDk5OTk5OTk4NgpBIDE1IEIgOTk5OTk5OTg1CkEgMTYgQiA5OTk5OTk5ODQKQSAxNyBCIDk5OTk5OTk4MwpBIDUwMDAwMDAwMCBCIDUwMDAwMDAwMApBIDUwMDAwMDAwMSBCIDUwMDAwMDAwMQ==
2 20
A 0 B 1000000000
A 1 B 999999999
A 2 B 999999998
A 3 B 999999997
A 4 B 999999996
A 5 B 999999995
A 6 B 999999994
A 7 B 999999993
A 8 B 999999992
A 9 B 999999991
A 10 B 999999990
A 11 B 999999989
A 12 B 999999988
A 13 B 999999987
A 14 B 999999986
A 15 B 999999985
A 16 B 999999984
A 17 B 999999983
A 500000000 B 500000000
A 500000001 B 500000001