#line 1 "main.cpp"
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <queue>
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"
class range {
struct iter {
std::size_t itr;
constexpr iter(std::size_t pos) noexcept: itr(pos) { }
constexpr void operator ++ () noexcept { ++itr; }
constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
constexpr std::size_t operator * () const noexcept { return itr; }
};
struct reviter {
std::size_t itr;
constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
constexpr void operator ++ () noexcept { --itr; }
constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
constexpr std::size_t operator * () const noexcept { return itr; }
};
const iter first, last;
public:
constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
constexpr iter begin() const noexcept { return first; }
constexpr iter end() const noexcept { return last; }
constexpr reviter rbegin() const noexcept { return reviter(*last - 1); }
constexpr reviter rend() const noexcept { return reviter(*first - 1); }
};
/**
* @title Range
*/
#line 16 "main.cpp"
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;
template <class T>
using Vec = std::vector<T>;
Vec<i64> solve(const Vec<std::pair<i64, i64>> &vec) {
std::priority_queue<i64> left;
left.push(-infty<i64>);
std::priority_queue<i64, Vec<i64>, std::greater<i64>> right;
right.push(infty<i64>);
Vec<i64> ret(vec.size() + 1);
i64 sum = 0;
for (auto i: range(0, vec.size())) {
const auto [s, t] = vec[i];
if (s <= right.top()) {
left.push(s);
sum -= s;
}
else {
right.push(s);
sum += s;
}
if (t <= right.top()) {
left.push(t);
sum -= t;
}
else {
right.push(t);
sum += t;
}
while (left.size() > right.size()) {
const auto x = left.top();
left.pop();
sum += x;
right.push(x);
sum += x;
}
while (left.size() + 1 < right.size()) {
const auto x = right.top();
right.pop();
sum -= x;
left.push(x);
sum -= x;
}
const auto med = right.top();
ret[i + 1] = sum + med * left.size() - med * right.size();
}
return ret;
}
int main() {
usize K, N;
std::cin >> K >> N;
Vec<std::pair<i64, i64>> vec;
vec.reserve(N);
i64 base_cost = 0;
while (N--) {
char p, q;
i64 s, t;
std::cin >> p >> s >> q >> t;
if (p == q) {
base_cost += std::abs(s - t);
}
else {
vec.emplace_back(s, t);
base_cost += 1;
}
}
std::sort(vec.begin(), vec.end(), [&](const auto &p, const auto &q) {
return p.first + p.second < q.first + q.second;
});
const auto pref = solve(vec);
i64 answer = pref.back();
if (K == 2) {
std::reverse(vec.begin(), vec.end());
const auto suff = solve(vec);
for (auto i: range(0, vec.size())) {
answer = std::min(answer, pref[i] + suff[vec.size() - i]);
}
}
std::cout << base_cost + answer << '\n';
return 0;
}
