Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Almost Permutation

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputRecently 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!

Input

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

Output

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible *cost* of the array.

Examples

Input

3 0

Output

3

Input

3 1

1 1 3 2

Output

5

Input

3 2

1 1 3 2

2 1 3 2

Output

9

Input

3 2

1 1 3 2

2 1 3 1

Output

-1

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/22/2019 19:30:45 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|