最近,Ivan 在调试代码时注意到了一个数组。现在 Ivan 不记得这个数组了,但是他试图修复的 bug 并没有消失,所以 Ivan 认为这个数组中的数据可能会帮助他重现这个 bug。
伊万清楚地记得数组中有n个元素,每个元素不小于1且不大于n。他还记得有关阵列的q个事实。伊万记得有两类事实:
- 1 li ri vi — 对于每个 x,使得 li ≤ x ≤ ri ax ≥ vi;
- 2 li ri vi — 对于每个 x,使得 li ≤ x ≤ ri ax ≤ vi。
Ivan 还认为这个数组是一个排列,但他对此不太确定。他想要恢复一些与他记住的q个事实相对应的数组,并且与排列非常相似。正式地,Ivan 将数组的成本表示如下:
$$cost = \sum_{i=1}^{n} (cnt(i))^2$$,其中 cnt(i) 是数组中 i 出现的次数。
帮助 Ivan 确定与事实相对应的数组的最小可能成本!
输入
第一行包含两个整数 n 和 q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100)。
接下来是 q 行,每行代表一个关于数组的事实。第 i 行包含第 i 个事实的数字 ti、li、ri 和 vi(1 ≤ ti ≤ 2、1 ≤ li ≤ ri ≤ n、1 ≤ vi ≤ n,ti 表示事实的类型)。
输出
如果事实存在争议并且没有与之对应的数组,则打印 -1。否则,打印数组的最小可能成本。
示例
输入 #1
3 0
输出 #1
3
输入 #2
3 1 1 1 3 2
输出 #2
5
输入 #3
3 2 1 1 3 2 2 1 3 2
输出 #3
9
输入#4
3 2 1 1 3 2 2 1 3 1
输出#4
-1