// 4
// failed.
//
//
// Why 10000 bytes...
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
template <class Node, class Detail>struct SegmentTreeTemplate{std::vector<Node> data;SegmentTreeTemplate(){}SegmentTreeTemplate(int number){assign(number);}SegmentTreeTemplate(std::size_t number){assign(number);}SegmentTreeTemplate(int number,Node const& node){assign(number,node);}void assign(int number){assign(number,Node{});}void assign(int number,Node const& node){assign(number,[&]{return node;});}void assign(int number,auto const& generator){data.reserve(number*2);data.resize(number);for(int i=0;i<number;++i) {if(data.size()>=data.capacity()) __builtin_unreachable();if constexpr(std::is_invocable_v<decltype(generator),int>){data.push_back(generator(i));}else{data.push_back(generator());}}for(int i=number;--i;) Detail::template combine<true>(data[i],data[i<<1],data[i<<1|1]);}private:static bool evaluatesToTrue(auto const& fn){if constexpr(std::is_same_v<decltype(fn()),void>){fn();return false;}else{return fn();}}
#define IS_TRUE(expr...) evaluatesToTrue([&]{return (expr);})
template<class F,class T>static decltype(auto) invokeWithOptionalLayer(F const& f,T&& t,int layer) {if constexpr(std::is_invocable_v<F,T&&>) return f(std::forward<T>(t));else return f(std::forward<T>(t),layer);}public:static void forStrictAncestorIndexDown(int node,auto const& fn){for(int shift=31^__builtin_clz(node);shift;--shift)if(IS_TRUE(fn(node>>shift))) break;}static void forStrictAncestorIndexUp(int node,auto const& fn){for(int y=node>>1;y;y>>=1)if(IS_TRUE(fn(y))) break;}static void forRangeIndex(int leftNode,int rightNode,auto const& leftfn,auto const& rightfn){int layer=0;while(leftNode<rightNode){if(leftNode&1) if(IS_TRUE(invokeWithOptionalLayer(leftfn,leftNode++,layer))) break;if(rightNode&1) if(IS_TRUE(invokeWithOptionalLayer(rightfn,--rightNode,layer))) break;leftNode>>=1;rightNode>>=1;++layer;}}
#undef IS_TRUE
int offset()const{return int(data.size()/2u);}void combineAll(int node){assert(node>=offset());forStrictAncestorIndexUp(node,[&](int it){Detail::template combine<false>(data[it],data[it<<1],data[it<<1|1]);});}void forRange(int leftNode,int rightNode,auto const& leftfn,auto const& rightfn){assert(leftNode>=offset());assert(rightNode>=offset());forRangeIndex(leftNode,rightNode,[&](auto it,auto layer){return invokeWithOptionalLayer(leftfn,data[it],layer);},[&](auto it,auto layer){return invokeWithOptionalLayer(rightfn,data[it],layer);});}void forRange(int leftNode,int rightNode,auto const& fn){forRange(leftNode,rightNode,fn,fn);}template<class T> T reduceRange(int leftNode,int rightNode,T initial,auto const& function) {forRange(leftNode,rightNode,[&](Node const& node){initial=function(std::move(initial),node);});return initial;}};
struct Node{ int count; int64_t sum; };
struct SegmentTree: SegmentTreeTemplate<Node, SegmentTree>{
using SegmentTreeTemplate::SegmentTreeTemplate;
static void push(Node&, Node&){ }
template<bool first>
static void combine(Node& parent, Node const& left, Node const& right){
parent.count=left.count+right.count;
parent.sum=left.sum+right.sum;
}
// other methods
void set(int node, Node value){
data[node]=value; combineAll(node);
}
void add(int index, int64_t value){
int node=index+offset();
set(node, {data[node].count+1, data[node].sum+value});
}
void remove(int index, int64_t value){
int node=index+offset();
assert(data[node].count); assert(data[node].sum>=value);
set(node, {data[node].count-1, data[node].sum-value});
}
Node get(int left, int right){
left+=offset(); right+=offset();
return reduceRange(left, right, Node{}, [](Node result, Node node){
Node next; combine<true>(next, result, node); return next;
});
}
int extract(int node, int pos) const{
assert(0<=pos and pos<=data[node].count);
if(pos==data[node].count){pos=0;++node;}
while(node<offset()){
node<<=1;
if(pos>=data[node].count){
pos-=data[node++].count;
}
}
return node;
}
int center(int left, int right){
auto const count=get(left, right).count;
if(count==0) return left;
assert(count%2==0); assert(count!=0);
int result=-1;
int left_=count/2, right_=count/2;
forRangeIndex(left+offset(), right+offset(),[&](int node){
if(data[node].count>=left_){
assert(result<0);
result=extract(node, left_);
return true;
}
left_-=data[node].count;
return false;
},[&](int node){
if(data[node].count>=right_){
assert(result<0);
result=extract(node, data[node].count-right_);
return true;
}
right_-=data[node].count;
return false;
});
assert(result>=offset());
if(result==offset()*2) result>>=1;
result-=offset();
assert(left<=result and result<=right);
assert(get(left, result).count==count/2);
assert(get(result, right).count==count/2);
return result;
}
};
struct Function{
std::vector<int64_t> allValues;
SegmentTree tree;
void build(){
std::sort(begin(allValues), end(allValues));
allValues.erase(std::unique(begin(allValues), end(allValues)), end(allValues));
assert(tree.data.empty());
tree.assign((int)allValues.size());
}
int64_t factor{};
void fakeAdd(std::pair<int, int> it){
allValues.push_back(it.first);
allValues.push_back(it.second);
}
void add(std::pair<int, int> it){
factor+=it.second-it.first;
assert(it.first<it.second);
for(auto it: {it.first, it.second}){
tree.add(int(std::lower_bound(begin(allValues), end(allValues), it)-begin(allValues)), it);
}
}
void remove(std::pair<int, int> it){
factor-=it.second-it.first;
assert(factor>=0);
assert(it.first<it.second);
for(auto it: {it.first, it.second}){
tree.remove(int(std::lower_bound(begin(allValues), end(allValues), it)-begin(allValues)), it);
}
}
int64_t calculateTwice(int64_t twicePos) {
auto info=tree.get(
int(std::upper_bound(begin(allValues), end(allValues), twicePos/2)-allValues.begin()),
tree.offset());
auto [countAll, sumAll]=tree.data[1];
assert(countAll%2==0);
assert(info.count<=countAll);
int64_t result=-sumAll+info.sum*2+twicePos*(countAll/2-info.count);
assert(([&]{
int64_t naive{};
for(int index=0; index<tree.offset(); ++index){
auto const c=tree.data[index+tree.offset()].count;
assert(c>=0);
naive+=c*(
std::abs(allValues[index]*2-twicePos)
);
}
assert(naive%2==0); naive/=2;
assert(naive==result);
return true;
}()));
return result-factor;
}
int64_t calculate(int64_t pos){return calculateTwice(pos*2);}
int64_t minPos() {
return allValues[tree.center(0, tree.offset())];
}
};
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 center=[&](auto it){return it.first+it.second;};
if(numBridge==2 and numPeople<=1000){
std::sort(begin(terms), end(terms),[&](auto first, auto sec){
return center(first)<center(sec);
});
auto result=INT64_MAX;
Function sumFunction, diffFunction, added, addFlipped;
for(auto t: terms){
sumFunction.fakeAdd(t);
added.fakeAdd(t);
addFlipped.fakeAdd(t);
diffFunction.fakeAdd(t);
addFlipped.fakeAdd({-t.second, t.first});
}
sumFunction.build();
diffFunction.build();
added.build();
addFlipped.build();
for(auto t: terms){
sumFunction.add(t);
added.add(t);
addFlipped.add(t);
}
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())
if(index!=0){
auto t=terms[index-1];
diffFunction.add(t);
addFlipped.add({-t.second, t.first});
sumFunction.remove(t);
addFlipped.remove(t);
}
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){
auto const twiced=std::max((int64_t)twicedleft,
std::min((int64_t)twicedright, (int64_t)added.minPos()*2));
result=std::min(result, sumFunction.calculateTwice(twiced)+diffFunction.calculateTwice(twiced));
}
else if(twiced<twicedleft){
auto const twicer=std::max<int64_t>(0, twicedleft+(int64_t)addFlipped.minPos()*2);
result=std::min(result, sumFunction.calculateTwice(twicedleft+twicer)+
diffFunction.calculateTwice(twicedleft-twicer));
}
else if(twiced>twicedright){
auto const twicer=std::max<int64_t>(0, twicedright+(int64_t)addFlipped.minPos()*2);
result=std::min(result, sumFunction.calculateTwice(twicedright+twicer)+
diffFunction.calculateTwice(twicedright-twicer));
}
}
std::cout<<result+base<<'\n';
}
}
