//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
// #define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// file("tbrackets");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
multiset<long long> ss;
struct Compare {
bool operator() (const long long& a, const long long& b) const {
return a > b;
}
};
long long n,k,a[200009],pre[200009],suf[200009];
multiset<long long,Compare> down;
multiset<long long> up;
long long sum=0,sum1=0,ans=0,sum2=0;
vector<pair<long long,long long>> pp;
void sub1(){
ans=0;
auto it=ss.begin();
if (ss.size()==0) return cout << sum2, void();
advance(it, ss.size()/2);
long long tam=*it;
for (long long x: ss){
ans+=abs(tam-x);
}
ans+=(ss.size()/2);
ans+=sum2;
cout << ans;
}
void sub2(){
if (ss.size()==0) return cout << sum2, void();
vector<long long> luu;
for (long long x: ss) luu.push_back(x);
// down.insert(a[0]);
// cout <<
long long sumr=0, suml=0;
for (long long i=0; i<luu.size(); i++){
// if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
// else {if (up.size()) up.erase(up.find(a[i-k]));}
// cout << i << ' ' << a[i-k] << "\n";
long long val=pp[i].first;
if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val;
else up.insert(val),sumr+=val;
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.find(tam)); suml-=tam; sumr+=tam;
up.insert(tam);
}
if (down.size()-up.size()==2) {
long long tam=*down.begin();
up.insert(*down.begin()); suml-=tam; sumr+=tam;
down.erase(down.find(tam));
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.find(tam)); suml+=tam; sumr-=tam;
down.insert(tam);
}
val=pp[i].second;
if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val;
else up.insert(val),sumr+=val;
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.find(tam)); suml-=tam; sumr+=tam;
up.insert(tam);
}
if (down.size()-up.size()==2) {
long long tam=*down.begin();
up.insert(*down.begin()); suml-=tam; sumr+=tam;
down.erase(down.find(tam));
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.find(tam)); suml+=tam; sumr-=tam;
down.insert(tam);
}
long long tam=*down.begin();
pre[i]=(sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml);
// cout << i << ": ";
// for (long long x: down) cout << x << ' ';
// cout << "\n";
// for (long long x: up) cout << x << ' ';
// cout << "\n";
}
// for (long long i=0; i<luu.size(); i++){
// cout << luu[i] << ' ' << pre[i] << "\n";
// }
down.clear(); up.clear();
sumr=0, suml=0;
for (long long i=pp.size()-1; i>=0; i--){
// if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
// else {if (up.size()) up.erase(up.find(a[i-k]));}
// cout << i << ' ' << a[i-k] << "\n";
long long val=pp[i].first;
if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val;
else up.insert(val),sumr+=val;
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.find(tam)); suml-=tam; sumr+=tam;
up.insert(tam);
}
if (down.size()-up.size()==2) {
long long tam=*down.begin();
up.insert(*down.begin()); suml-=tam; sumr+=tam;
down.erase(down.find(tam));
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.find(tam)); suml+=tam; sumr-=tam;
down.insert(tam);
}
val=pp[i].second;
if (val<*up.begin() || up.size()==0) down.insert(val),suml+=val;
else up.insert(val),sumr+=val;
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.find(tam)); suml-=tam; sumr+=tam;
up.insert(tam);
}
if (down.size()-up.size()==2) {
long long tam=*down.begin();
up.insert(*down.begin()); suml-=tam; sumr+=tam;
down.erase(down.find(tam));
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.find(tam)); suml+=tam; sumr-=tam;
down.insert(tam);
}
long long tam=*down.begin();
suf[i]=(sumr - 1LL*tam*up.size()) + (1LL*tam*down.size() - suml);
// cout << i << ':';
// for (long long x: down) cout << x << ' ';
// cout << "\n";
// for (long long x: up) cout << x << ' ';
// cout << "\n";
}
ans=INF;
for (long long i=0; i<pp.size()-1; i++){
ans=min(ans,pre[i]+suf[i+1]);
}
// cout << ans << "\n";
ans+=(ss.size()/2);
ans+=sum2;
cout << ans;
}
bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
return a.first + a.second < b.first + b.second;
}
void solve(){
long long k,n;
cin >> k >> n;
for (long long i=1; i<=n; i++){
char ch1,ch2;
long long x,y;
cin >> ch1 >> x >> ch2 >> y;
if (ch1!=ch2) {
ss.insert(x); ss.insert(y); pp.push_back({x, y});
sum+=x+y;
}
else sum1+=2,sum2+=abs(y-x);
// pp.push_back({x, y});
}
sort(all(pp),cmp);
if (k==1) sub1();
else sub2();
}
