F. 几乎排列

每次测试的时间限制：3 秒
每次测试的内存限制：512 兆字节

最近，伊万在调试代码时注意到了一个数组 $a$。现在伊万记不清这个数组了，但他试图修复的漏洞仍然存在，因此伊万认为这个数组中的数据可能有助于他重现这个 bug。

伊万清楚地记得数组中有 $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$。

伊万认为这个数组可能是一个排列，但他不太确定。他想恢复一个满足上述 $q$ 条事实、并且尽可能“接近”排列的数组。形式化地，伊万定义数组的代价为：

其中 $\text{cnt}(i)$ 是数字 $i$ 在数组中出现的次数。

请帮助伊万确定满足所有事实的数组的最小可能代价。

输入
第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 50$，$0 \le q \le 100$）。
接下来 $q$ 行，每行描述一条事实。第 $i$ 行的格式为 $t_i, l_i, r_i, v_i$（$1 \le t_i \le 2$，$1 \le l_i \le r_i \le n$，$1 \le v_i \le n$，$t_i$ 表示事实的类型）。

输出
如果这些事实相互矛盾，不存在任何满足条件的数组，则输出 $-1$。
否则，输出满足所有事实的数组的最小可能代价。

示例

输入

3 0

输出

3

输入

3 1
1 1 3 2

输出

5

输入

3 2
1 1 3 2
2 1 3 2

输出

9

输入

3 2
1 1 3 2
2 1 3 1

输出

-1