0098 - 学食

問題

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

• 行列にはそれぞれ 1 から N までの番号が振られた N 人が並びます。
• C 個の高校生のペア (a_i, b_i) それぞれについて、以下の２種類の制約があります：
  • １つ目の制約は順序に関するもので以下のいずれかです：
    a_i は b_i よりも先、または同じ位置に並ばなくてはならない
    a_i は b_i よりも後、または同じ位置に並ばなくてはならない
    a_i は b_i より先でも、同じ位置でも、後でもよい
    
  • ２つ目の制約は距離に関するもので以下のいずれかです：
    a_i と b_i は d_i メートル以上離れなければならない
    a_i と b_i は d_i メートル以内に並ばなければならない
    

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

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

入力

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

N C
constraint1
constraint2
:
constraintC

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

aioibisidi

制約には空白は含まれない。a_i, o_i, b_i, s_i, d_i の意味を以下に示す。

• a_i と b_i (1 ≤ a_i, b_i ≤ N かつ a_i ≠ b_i ) は高校生の番号、d_i は距離 (0 ≤ d ≤ 10000) を表す整数である。
• o_i は順序の制約を指定する <=、>=、* のいずれかの文字列であり、<= の場合「a_i は b_i よりも先、または同じ位置に並ばなくてはならない」、>= の場合「a_i は b_i よりも後、または同じ位置に並ばなくてはならない」、* の場合「a_i は b_i より先でも、同じ位置でも、後でもよい」ことを意味する。ただし o_i が * となる制約は７個以上与えられることはない。
• s_i は距離の制約を指定する + または - の文字であり、+ の場合「a_i と b_i は d_i メートル以上離れなければならない」、- の場合「a_i と b_i は d_i メートル以内に並ばなければならない」ことを意味する。

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

出力

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

入出力例

入力例１

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

出力例１

3

入力例２

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

出力例２

-1

入力例３

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

出力例３

inf