该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】

$N$ 只猴子，依次编号为 $1$ ~ $N$。

现在要给它们分发一些小球。每个猴子至少要分到一个小球。同时猴子们提出了 M 个要求需要满足，要求格式及含义见输入格式。

问：至少需要准备多少个小球？

【输入格式】

第一行：两个整数 N, M

接下来 M 行：每行三个整数 C, i, j，具体含义如下：(假设编号为 i 的猴子分到的小球数是 Ai)

• 如果 C = 1，表示 Ai = Aj
• 如果 C = 2，表示 Ai < Aj
• 如果 C = 3，表示 Ai ≥ Aj
• 如果 C = 4，表示 Ai > Aj
• 如果 C = 5，表示 Ai ≤ Aj

【输出格式】

一个整数，表示最少需要准备的小球个数。若无解，则输出 -1。

【输入样例】

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

【输出样例】

11

【数据范围】

30% 的数据：$N ≤ 100$

100% 的数据：$N, M ≤ 10^5, 1 ≤ C ≤ 5, 1 ≤ i, j ≤ N$。