// 4
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
struct Function{
std::vector<int> changes; // by 2, must be even
std::vector<int64_t> value;
int64_t value0{};
void add(std::pair<int, int> it){
changes.push_back(it.first);
changes.push_back(it.second);
assert(it.first<=it.second);
value0+=2*(0<it.first ? it.first-0: 0>it.second ? 0-it.second: 0);
}
void build(){
std::sort(begin(changes), end(changes));
assert(value.empty());
if(changes.empty()) {
assert(value0==0);
return;
}
value.resize(changes.size());
int slope=-(int)changes.size();
value[0]=0;
for(int index=1; index<(int)changes.size(); ++index){
slope+=2;
value[index]=value[index-1]+slope*int64_t(changes[index]-changes[index-1]);
}
slope+=2;
assert(slope==(int)changes.size());
auto const delta=value0-calculate(0);
for(auto& it: value) it+=delta;
assert(calculate(0)==value0);
}
int64_t calculateTwice(int64_t twicePos) const{
assert(changes.size()%2==0);
if(changes.empty()) {
assert(value0==0);
return 0;
}
auto index=int(std::lower_bound(begin(changes), end(changes), (twicePos+1)>>1)-begin(changes));
if(index==(int)changes.size()){
return value.back()+int64_t(changes.size()/2)*(twicePos-changes.back()*2);
}else{
return value[index]-int64_t(changes[index]*2-twicePos)*(index-int64_t(changes.size()/2));
}
}
int64_t calculate(int64_t pos){return calculateTwice(pos*2);}
int minPos() const{
assert(changes.size()%2==0);
return changes.empty() ? 0: changes[changes.size()/2];
}
// a(x), b(x) -> (x -> a(x)+b(x))
template<bool flip=false>
Function add(Function const& other) const{
Function result;
for(auto it: changes) result.changes.push_back(it);
for(auto it: other.changes) result.changes.push_back(flip ? -it: it);
result.value0=value0+other.value0;
result.build();
return result;
}
// a(x), b(x) -> (x -> a(x)+b(-x))
Function addFlipSecond(Function const& other) const{
return add<true>(other);
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int numBridge, numPeople; std::cin>>numBridge>>numPeople;
int64_t base{};
std::vector<std::pair<int, int>> terms; terms.reserve(numPeople);
for(int _=0; _<numPeople; ++_){
char side1, side2; int pos1, pos2;
std::cin>>side1>>pos1>>side2>>pos2;
std::tie(pos1, pos2)=std::minmax({pos1, pos2});
if(side1==side2) base+=pos2-pos1;
else {
base+=pos2-pos1+1;
terms.push_back({pos1, pos2});
}
}
assert((int)terms.size()<=numPeople);
if(terms.empty()){std::cout<<base<<'\n'; return 0;}
std::vector<int> positions; positions.reserve(terms.size()*2);
for(auto [first, sec]: terms){
positions.push_back(first); positions.push_back(sec);
}
std::sort(begin(positions), end(positions));
positions.erase(std::unique(begin(positions), end(positions)), end(positions));
/*
auto const calculate=[&](int pos){
int64_t result{};
for(auto [first, sec]: terms){
if(pos<first) result+=first-pos;
else if(pos>sec) result+=pos-sec;
}
return result*2;
};
if(numBridge==1){
int index=0; auto curValue=calculate(positions[0]);
for(int step=1<<30; step>>=1;){
auto const check=[&](int next){
if((unsigned) next<positions.size()){
auto const nextValue=calculate(positions[next]);
if(nextValue<curValue){index=next; curValue=nextValue;}
}
};
check(index-step); check(index+step);
}
std::cout<<curValue+base<<'\n';
}
*/
auto const center=[&](auto it){return it.first+it.second;};
if(numBridge==2){
std::sort(begin(terms), end(terms),[&](auto first, auto sec){
return center(first)<center(sec);
});
auto result=INT64_MAX;
for(int index=0; index<=(int)terms.size(); ++index){
int twicedleft=index==0 ? INT_MIN: center(terms[index-1]);
int twicedright=index==(int)terms.size() ? INT_MAX: center(terms[index]);
// consider d in [twicedleft/2..twicedright/2]
// left terms=(0..index), right terms=(index..(int)terms.size())
Function sumFunction, diffFunction;
for(int i=0; i<index; ++i)
diffFunction.add(terms[i]);
for(int i=index; i<(int)terms.size(); ++i)
sumFunction.add(terms[i]);
sumFunction.build();
diffFunction.build();
auto sum1=sumFunction.minPos(), diff1=diffFunction.minPos(); // d+r, d-r
auto twiced=sum1+diff1, twicer=sum1-diff1;
if(twicer>=0 and twicedleft<=twiced and twiced<=twicedright){
result=std::min(result, sumFunction.calculate(sum1)+diffFunction.calculate(diff1));
}
else if(twicer<0){
// in this branch, sometimes it's not necessary to binary search...
Function functionr0=sumFunction.add(diffFunction); // d -> value|d=d, r=0
auto const twiced=std::max((int64_t)twicedleft,
std::min((int64_t)twicedright, (int64_t)functionr0.minPos()*2));
result=std::min(result, sumFunction.calculateTwice(twiced)+diffFunction.calculateTwice(twiced));
}
else if(twiced<twicedleft){
Function f=sumFunction.addFlipSecond(diffFunction);
auto const twicer=std::max<int64_t>(0, twicedleft+(int64_t)f.minPos()*2);
result=std::min(result, sumFunction.calculateTwice(twicedleft+twicer)+
diffFunction.calculateTwice(twicedleft-twicer));
}
else if(twiced>twicedright){
Function f=sumFunction.addFlipSecond(diffFunction);
auto const twicer=std::max<int64_t>(0, twicedright+(int64_t)f.minPos()*2);
result=std::min(result, sumFunction.calculateTwice(twicedright+twicer)+
diffFunction.calculateTwice(twicedright-twicer));
}
}
std::cout<<result+base<<'\n';
}
}
