Almost Permutation

Recently Ivan은 자신의 코드를 디버깅하던 중 배열 a를 발견했다. Now Ivan은 이 배열을 기억하지 못하지만, 고치려던 버그가 사라지지 않았기 때문에 Ivan은 이 배열의 데이터가 버그를 재현하는 데 도움이 될 수도 있다고 생각한다.

Ivan은 배열에 n개의 원소가 있었고, 각 원소가 1보다 작지 않고 n보다 크지 않았다는 것을 분명히 기억한다. 또한 그는 배열에 관한 q개의 사실을 기억한다. Ivan이 기억하는 사실에는 두 가지 유형이 있다:

• 1 li ri vi — li ≤ x ≤ ri인 각 x에 대해 ax ≥ vi이다;
• 2 li ri vi — li ≤ x ≤ ri인 각 x에 대해 ax ≤ vi이다.

Also Ivan은 이 배열이 순열이었다고 생각하지만, 그다지 확신하지는 못한다. 그는 자신이 기억하는 q개의 사실에 부합하면서 순열과 매우 유사한 어떤 배열을 복원하려 한다. 형식적으로 Ivan은 배열의 비용을 다음과 같이 정의했다:

, 여기서 cnt(i)는 배열에서 i이 등장하는 횟수이다.

사실에 부합하는 배열의 가능한 최소 비용을 구하라Help Ivan!

첫 번째 줄에는 두 정수 n과 q가 주어진다 (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).

이어서 배열에 관한 사실을 각각 나타내는 q개의 줄이 주어진다. i-th번째 줄에는 i-th번째 사실을 나타내는 수 ti, li, ri, vi가 주어진다 (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n, 1 ≤ vi ≤ n, ti denotes the type of the fact).

사실들이 서로 모순되어 이에 부합하는 배열이 없다면 -1을 출력한다. 그렇지 않으면 배열의 가능한 최소 비용을 출력한다.