← 返回题目列表

Codeforces · 863/F

F. 几乎排列

中文机器翻译题面 查看原题

最近,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