/*
0 0 :
0 1
1 1
*/
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
int k, n;
lld ans;
vector< pair< int, int > > seg;
vector< int > pos;
void init() {
cin >> k >> n;
seg.reserve( n );
for ( int i = 0 ; i < n ; ++ i ) {
string P; int S;
string Q; int T;
cin >> P >> S >> Q >> T;
ans += ( P == Q ? abs( S - T ) : 1 );
if ( P != Q ) seg.push_back( minmax( S, T ) );
}
pos.reserve( seg.size() << 1 );
for ( auto [ L, R ] : seg )
pos.push_back( L ),
pos.push_back( R );
}
struct Data{
lld val; int P, Q;
priority_queue< pair< int, size_t > >
LPRQ, PLR, LRQ, PLQR, PQLR;
vector< size_t > LRPQ;
lld sLRPQ, sLPRQ, sPLR, sLRQ, sPLQR, sPQLR;
Data() : val( 0 ), sLRPQ( 0 ),
sLPRQ( 0 ), sPLR( 0 ),
sLRQ( 0 ), sPLQR ( 0 ),
sPQLR( 0 ) {}
void calcVal() {
val = 0;
val += sPQLR - ( ( lld ) 2 ) * Q * PQLR.size();
val += sPLQR;
val += ( ( lld ) 2 ) * Q * LRQ.size() - sLRQ;
val += sPLR - ( ( lld ) 2 ) * P * PLR.size();
val += sLPRQ;
val += ( ( lld ) 2 ) * P * LRPQ.size() - sLRPQ;
}
void build() {
P = pos[ 0 ], Q = pos[ 0 ];
for ( size_t i = 0 ; i < seg.size() ; ++ i ) {
PQLR.push( { -seg[ i ].first, i } );
sPQLR += seg[ i ].first + seg[ i ].second;
}
calcVal();
}
void adjustPQLR() {
while ( not PQLR.empty() ) {
if ( -PQLR.top().first > Q )
break;
size_t idx = PQLR.top().second; PQLR.pop();
sPQLR -= seg[ idx ].first + seg[ idx ].second;
PLQR.push( { -seg[ idx ].second, idx } );
sPLQR += seg[ idx ].second - seg[ idx ].first;
}
}
void adjustPLQR() {
while ( not PLQR.empty() ) {
if ( -PLQR.top().first > Q )
break;
size_t idx = PLQR.top().second; PLQR.pop();
sPLQR -= seg[ idx ].second - seg[ idx ].first;
LRQ.push( { - seg[ idx ].first - seg[ idx ].second, idx } );
sLRQ += seg[ idx ].first + seg[ idx ].second;
}
}
void adjustLRQ() {
while ( not LRQ.empty() ) {
if ( -LRQ.top().first > ( P + Q ) )
break;
size_t idx = LRQ.top().second; LRQ.pop();
sLRQ -= seg[ idx ].first + seg[ idx ].second;
PLR.push( { -seg[ idx ].first, idx } );
sPLR += seg[ idx ].first + seg[ idx ].second;
}
}
void adjustPLR() {
while ( not PLR.empty() ) {
if ( -PLR.top().first > P )
break;
size_t idx = PLR.top().second; PLR.pop();
sPLR -= seg[ idx ].first + seg[ idx ].second;
LPRQ.push( { -seg[ idx ].second, idx } );
sLPRQ += seg[ idx ].second - seg[ idx ].first;
}
}
void adjustLPRQ() {
while ( not LPRQ.empty() ) {
if ( -LPRQ.top().first > P )
break;
size_t idx = LPRQ.top().second; LPRQ.pop();
sLPRQ -= seg[ idx ].second - seg[ idx ].first;
LRPQ.push_back( idx );
sLRPQ += seg[ idx ].first + seg[ idx ].second;
}
}
void addP( int x ) {
P = x;
adjustPQLR();
adjustPLQR();
adjustLRQ();
adjustPLR();
adjustLPRQ();
calcVal();
}
void addQ( int x ) {
Q = x;
adjustPQLR();
adjustPLQR();
adjustLRQ();
adjustPLR();
adjustLPRQ();
calcVal();
}
friend ostream& operator<<( ostream& os, const Data& d ) {
return os << "P = " << d.P << ", Q = " << d.Q << ", val = " << d.val << ", sLRPQ = " << d.sLRPQ << ", sLPRQ = " << d.sLPRQ << ", sPLR = " << d.sPLR << ", sLRQ = " << d.sLRQ << ", sPLQR = " << d.sPLQR << ", sPQLR = " << d.sPQLR;
}
} cur, nxt;
function< void() > solve[] = {
[] () {
nth_element( pos.begin(), next( pos.begin(), pos.size() >> 1 ), pos.end() );
for ( int x : pos )
ans += abs( x - *next( pos.begin(), pos.size() >> 1 ) );
},
[] () {
if ( pos.size() < 2 ) {
solve[ 0 ]();
return;
}
lld dlt = numeric_limits< lld >::max();
sort( pos.begin(), pos.end() );
cur.build();
nxt.build();
cur.addQ( pos[ 0 ] );
nxt.addQ( pos[ 1 ] );
size_t Q = 0;
for ( size_t P = 0 ; P < pos.size() ; ++ P ) {
while ( Q < P ) {
cur.addQ( pos[ ++ Q ] );
if ( Q + 1 < pos.size() )
nxt.addQ( pos[ Q + 1 ] );
}
cur.addP( pos[ P ] );
nxt.addP( pos[ P ] );
while ( Q + 1 < pos.size() and cur.val >= nxt.val ) {
cur.addQ( pos[ ++ Q ] );
if ( Q + 1 < pos.size() )
nxt.addQ( pos[ Q + 1 ] );
}
dlt = min( dlt, cur.val );
// cout << "cur: " << cur << '\n';
// cout << "nxt: " << nxt << '\n';
}
ans += dlt;
}
};
int main() {
ios_base::sync_with_stdio( false );
cin.tie( nullptr );
init();
solve[ k - 1 ]();
cout << ans << '\n';
return 0;
}
/*
L R P Q -> R <= P P - L + P - R
L P R Q -> L <= P and P <= R R - L
P L R Q -> P <= L and R <= Q and ( L + R ) <= ( P + Q ) L - P + R - P
P L R Q -> P <= L and R <= Q and ( L + R ) >= ( P + Q ) Q - R + Q - L
P L Q R -> L <= Q and Q <= R R - L
P Q L R -> Q <= L L - Q + R - Q
( L + R ) <= ( P + Q )
*/
