糖果：[SCOI2011]

[SCOI2011]糖果

题目描述

在幼儿园里共有N名小朋友,lxhgww老师正在为这些幼儿分配糖块,每位孩子都需要至少获得一块糖块。然而由于孩子们具有强烈的竞争意识,他们经常会对彼此提出不平等的要求,例如有一个条件是小明认为自己得到的糖块数不应少于小红的数量。当进行糖块分配时,lxhgww老师需要确保所有幼儿提出的K项条件都能得到满足,而由于幼儿园中的糖块数量有限,他必须计算出最少需要准备多少颗糖块才能既保证每位孩子都能拿到至少一块又能够满足所有幼儿提出的各项条件

输入输出格式

输入格式：

输入的第一行包含两个整数N和K。其后K行详细规定了这些关系的具体要求：每行包含三个数值X、A、B（其中1≤A,B≤N）。具体来说：

• 当X=1时，则规定第A位小朋友分发的数量与第B位小朋友完全一致；
• 当X=2时，则规定第A位小朋友获得的数量必须少于第B位朋友；
• 当X=3时，则规定第A位小朋友获得的数量不得低于第B位朋友；
• 当X=4时，则规定第A位小朋友获得的数量须高于第B位朋友；
• 当X=5时，则规定第A位小朋友获得的数量最多只能与之持平。

输出格式：

用作标记lxhgww老师至少需要准备的糖果数。如果无法满足所有小朋友的需求，则返回值为-1

输入输出样例

输入样例#1：

5 71 1 22 3 24 4 13 4 5