Almost Permutation

题意翻译

现有一个长度为 $n$ 的未知数组 $A$ , 每个元素都是 $[1,n]$ 内的整数。 有如下两种共 $q$ 个限制 : 1. $[l,r]$ 中所有数都大于等于 $v$ 2. $[l,r]$ 中所有数都小于等于 $v$ 设 $cnt(i)$ 为 $i$ 在 $A$ 中的出现次数。 求出在所有满足条件的数组中,下列式子的最小值 : $$\sum\limits_{i=1}^ncnt(i)^2$$ 若不存在满足条件的数组,输出 $-1$。

题目描述

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!

输入输出格式

输入格式

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).

输出格式

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

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