CF863F.Almost Permutation

Recently Ivan noticed an array a while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.

Ivan clearly remembers that there were n elements in the array, and each element was not less than 1 and not greater than n. Also he remembers q facts about the array. There are two types of facts that Ivan remembers:

• 1 l__i r__i v__i — for each x such that l__i ≤ x ≤ r__i a__x ≥ v__i;
• 2 l__i r__i v__i — for each x such that l__i ≤ x ≤ r__i a__x ≤ v__i.

Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the q facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the cost of array as follows:

, where cnt(i) is the number of occurences of i in the array.

Help Ivan to determine minimum possible cost of the array that corresponds to the facts!

最近，Ivan 在调试代码时注意到了一个数组 $a$。如今 Ivan 已经记不清这个数组的具体内容了，但他试图修复的 bug 仍未解决，因此 Ivan 认为该数组中的数据或许能帮助他复现这个 bug。

Ivan 清晰地记得：该数组包含 $n$ 个元素，且每个元素均不小于 $1$、不大于 $n$。此外，他还记得关于该数组的 $q$ 条事实。这些事实分为两类：

• 1 l_i r_i v_i — 对每个满足 $l_i \le x \le r_i$ 的下标 $x$，均有 $a_x \ge v_i$；
• 2 l_i r_i v_i — 对每个满足 $l_i \le x \le r_i$ 的下标 $x$，均有 $a_x \le v_i$。

此外，Ivan 认为该数组原本是一个排列（permutation），但对此并不十分确定。他希望还原出一个满足上述 $q$ 条事实的数组，且该数组应尽可能“接近”一个排列。形式化地，Ivan 将数组的**代价（cost）**定义如下：

，其中 $\text{cnt}(i)$ 表示数值 $i$ 在数组中出现的次数。

请帮助 Ivan 求出满足所有事实的数组的最小可能代价！

The first line contains two integer numbers n and q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).

Then q lines follow, each representing a fact about the array. i-th line contains the numbers t__i, l__i, r__i and v__i for i-th fact (1 ≤ t__i ≤ 2, 1 ≤ l__i ≤ r__i ≤ n, 1 ≤ v__i ≤ n, t__i denotes the type of the fact).

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 50$，$0 \leq q \leq 100$）。

接下来是 $q$ 行，每行表示一条关于该数组的事实。第 $i$ 行包含数字 $t_i$、$l_i$、$r_i$ 和 $v_i$，对应第 $i$ 条事实（$1 \leq t_i \leq 2$，$1 \leq l_i \leq r_i \leq n$，$1 \leq v_i \leq n$；其中 $t_i$ 表示该事实的类型）。

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible cost of the array.

如果这些事实存在争议，且不存在与之对应的数组，则输出 -1。否则，输出该数组的最小可能 cost。