CF863F Almost Permutation

最近，Ivan 在调试他的代码时注意到了一个数组 $a$。现在 Ivan 已经记不起这个数组了，但他试图修复的 bug 依然没有消失，所以 Ivan 认为这个数组中的数据也许能帮助他重现 bug。 Ivan 清楚地记得，这个数组有 $n$ 个元素，并且每个元素都不小于 $1$ 且不大于 $n$。此外，他还记得关于这个数组的 $q$ 条信息。Ivan 记得的信息共有两种类型： - $1$ $l_{i}$ $r_{i}$ $v_{i}$ —— 对所有 $x$ 满足 $l_{i} \leq x \leq r_{i}$，有 $a_{x} \geq v_{i}$； - $2$ $l_{i}$ $r_{i}$ $v_{i}$ —— 对所有 $x$ 满足 $l_{i} \leq x \leq r_{i}$，有 $a_{x} \leq v_{i}$。 Ivan 认为这个数组很可能是一个排列，但他并不确定。他希望恢复出一个同时满足这 $q$ 条信息并且“非常接近排列”的数组。更正式地，Ivan 将数组的 $cost$ 定义为：  其中 $cnt(i)$ 表示 $i$ 在数组中出现的次数。 请帮助 Ivan 求出满足这些条件的数组的最小可能 $cost$。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 50$，$0 \leq q \leq 100$）。 接下来 $q$ 行，每行描述一条关于数组的信息。第 $i$ 行包含 $t_{i}, l_{i}, r_{i}, v_{i}$（$1 \leq t_{i} \leq 2$，$1 \leq l_{i} \leq r_{i} \leq n$，$1 \leq v_{i} \leq n$，$t_{i}$ 表示信息的类型）。

如果这些信息相互矛盾，不存在满足条件的数组，输出 $-1$。否则，输出数组的最小可能 $cost$。

由 ChatGPT 5 翻译