There are $N$ children in a kindergarten, and teacher lxhgww wants to distribute candies to them, ensuring that every child receives at least one candy.

However, the children are prone to jealousy and often make requests. For example, Xiao Ming might not want Xiao Hong to receive more candies than he does. In total, lxhgww needs to satisfy $K$ such requests while distributing the candies.

Since the supply of candies is limited, lxhgww wants to know the minimum number of candies he needs to prepare to ensure that every child receives at least one candy and all the children's requests are satisfied.

Input

The first line contains two integers $N$ and $K$.

The next $K$ lines describe the relationships that must be satisfied. Each line contains three integers $X, A, B$:

• If $X=1$, the number of candies received by child $A$ must be equal to the number of candies received by child $B$.
• If $X=2$, the number of candies received by child $A$ must be less than the number of candies received by child $B$.
• If $X=3$, the number of candies received by child $A$ must be no less than the number of candies received by child $B$.
• If $X=4$, the number of candies received by child $A$ must be more than the number of candies received by child $B$.
• If $X=5$, the number of candies received by child $A$ must be no more than the number of candies received by child $B$.

Output

Output a single line representing the minimum number of candies teacher lxhgww needs to prepare. If it is impossible to satisfy all the children's requests, output $-1$.

Examples

Input 1

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

Output 1

11

Subtasks

For $30\%$ of the data, $N < 100$.

For $100\%$ of the data, $N < 100\,000$, $K \le 100\,000$, $1 \le X \le 5$, $1 \le A, B \le N$.