#include <bits/stdc++.h>
using namespace std;
using lint = long long;
lint solve(lint K, vector<pair<lint, lint>> A) {
if (A.empty())
return 0;
lint N = A.size();
vector<lint> points;
sort(A.begin(), A.end(), [&](pair<lint, lint> l, pair<lint, lint> r) {
return l.first + l.second < r.first + r.second;
});
auto running_median = [&](vector<pair<lint, lint>> A) {
multiset<lint> sml;
multiset<lint> big;
lint sum_sml = 0, sum_big = 0;
vector<lint> res(N + 1, 0);
for (int i = 1; i <= N; i++) {
sml.emplace(A[i - 1].first);
sum_sml += A[i - 1].first;
big.emplace(A[i - 1].second);
sum_big += A[i - 1].second;
while (*sml.rbegin() > *big.begin()) {
sum_sml += *big.begin() - *sml.rbegin();
sum_big += *sml.rbegin() - *big.begin();
big.emplace(*sml.rbegin());
sml.emplace(*big.begin());
sml.erase(prev(sml.end()));
big.erase(big.begin());
}
res[i] = sum_big - sum_sml;
}
return res;
};
vector<lint> prefix_median = running_median(A);
reverse(A.begin(), A.end());
vector<lint> suffix_median = running_median(A);
reverse(A.begin(), A.end());
lint res = INT64_MAX;
for (int cur = 0; cur <= N; cur++) {
res = min(res, prefix_median[cur] + suffix_median[N - cur]);
}
if (K == 1)
res = prefix_median[N];
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
lint K, N, ans = 0;
vector<pair<lint, lint>> A;
cin >> K >> N;
for (int i = 0; i < N; i++) {
char Z1, Z2;
lint B1, B2;
cin >> Z1 >> B1 >> Z2 >> B2;
if (B1 > B2) swap(B1, B2);
if (Z1 == Z2)
ans += B2 - B1;
else
A.emplace_back(B1, B2);
}
cout << ans + A.size() + solve(K, A) << "\n";
return 0;
}
