School Cafeteria

Time Limit : 1 sec, Memory Limit : 65536 KB

学食

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

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

また、先頭から同じ距離の場所に複数の人が並ぶことができ、行列の先頭には常に番号 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 の意味を以下に示す。

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

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

出力

先頭から最後尾までの距離を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 

Source: PC Koshien 2014, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-9-13
http://web-ext.u-aizu.ac.jp/pc-concours/