学食

今日はZ大学のオープンキャンパスです。毎年この日の昼休みには、大勢の高校生たちが学食に列をつくります。そこでZ大学の事務局は、行列の長さが最大でどのくらいの距離になるかを予測することにしました。事前調査の結果で、以下のことが分かっています。

また、先頭から同じ距離の場所に複数の人が並ぶことができ、行列の先頭には常に番号 1 の人が並ぶことが分かっています。

与えられた C 個の制約をすべて満たす行列について、先頭から最後尾までの距離が最大となるような並び方をした場合の距離を求めるプログラムを作成してください。ただし、どこまでも離れることができる場合は inf と、制約を満たす並び方が不可能な場合は -1 と出力してください。

入力

入力は以下の形式で与えられる。

N C
constraint1
constraint2
:
constraintC

1 行目に行列に並ぶ高校生の人数 N (2 ≤ N ≤ 100) と制約の数 C (0 ≤ C ≤ 200) が与えられる。続く C 行に各制約 constrainti が次の形式で与えられる。

aioibisidi

制約には空白は含まれない。ai, oi, bi, si, di の意味を以下に示す。

ただし、あるペアに対して複数の制約が与えられることはないものとする。

出力

先頭から最後尾までの距離を1行に出力する。

入出力例


入力例1

3 2
1<=2-1
2<=3-2

出力例1

3

入力例2

3 3
1<=2-1
2<=3-2
1<=3+4

出力例2

-1

入力例3

3 2
1<=2-2
2*3+1

出力例3

inf