Problem: Today is the open campus of Z University. Every year during the lunch break on this day, many high school students line up for the school cafeteria. Therefore, the secretariat of Z University decided to predict the maximum distance of the procession. As a result of the preliminary survey, we know the following.

* The matrix is ​​lined with N people, each numbered from 1 to N.
* For each pair of C high school students (ai, bi), there are two types of restrictions:
* The first constraint is on the order and is one of the following:
ai must be ahead of bi or in the same position
ai must line up after or in the same position as bi
ai can be before, in the same position, or after bi

* The second constraint is on distance and is one of the following:
ai and bi must be at least di meters apart
ai and bi must line up within di meters




We also know that multiple people can be lined up at the same distance from the beginning, and that the number 1 person is always at the beginning of the procession.

Create a program to find the distance when the matrix that satisfies all the given C constraints is arranged so that the distance from the beginning to the end is the maximum. However, output inf if it can be separated indefinitely, and -1 if it is not possible to arrange in a way that satisfies the constraint.



input

The input is given in the following format.


N C
constraint1
constraint2
::
constraintC


The number of high school students in the queue on the first line N (2 ≤ N ≤ 100) and the number of constraints C (0 ≤ C ≤ 200) are given. Each constraint constrainti is given in the following C line in the following format.


aioibisidi


The constraint does not include spaces. The meanings of ai, oi, bi, si and di are shown below.

* ai and bi (1 ≤ ai, bi ≤ N and ai ≠ bi) are high school student numbers, and di is an integer representing the distance (0 ≤ d ≤ 10000).
* oi is a string of <=,> =, * that specifies the order constraint, and if <=, "ai must precede bi or be in the same position",> = In the case of, "ai must be after bi or in the same position", and in the case of *, it means that "ai can be before, in the same position, or after bi". However, no more than 7 constraints with oi as * can be given.
* si is the + or-character that specifies the distance constraint, for + "ai and bi must be at least di meters apart", for-"ai and bi must be within di meters" It means that.



However, it is assumed that multiple constraints are not given to a pair.

output

The distance from the beginning to the end is output on one line.

Example

Input

3 2
1


Output

3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/*
*の制約が6個までということは全パターンやれということ？
双対問題を考える
制約通り辺を張ってベルマンフォードして負辺でinf
到達不可能で-1でいいのかな
*/
template<typename T>
struct edge{
    int src,to;//src source
    T cost;
    edge(int to,T cost):src(-1),to(to),cost(cost){}
    edge(int src,int to,T cost):src(src),to(to),cost(cost){}
};

//空を返したら負のループ
template<typename T>
vector<T> BellmanFord(vector<edge<T>> &edges,int V,int s){
    const auto TINF=numeric_limits<T>::max();
    vector<T> dist(V,TINF);
    dist[s]=0;
    for(int i=0;i<V-1;i++){
        for(auto &e:edges){
            if(dist[e.src]==TINF) continue;
            dist[e.to]=min(dist[e.to],dist[e.src]+e.cost);
        }
    }
    for(auto &e:edges){
        if(dist[e.src]==TINF) continue;
        if(dist[e.src]+e.cost<dist[e.to]) return vector<T>();
    }
    return dist;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int N,C;cin>>N>>C;
    vector<edge<int>> es;
    vector<tuple<int,int,int,int>> undif;
    rep(i,C){
        string s;cin>>s;
        int u=0,v=0,o,w=0,pl=0;//o=-1は<=,o=0は*,o=1は>=  plは1が+，0が-
        int idx=0;
        for(;;){
            if(0<=(s[idx]-'0') and (s[idx]-'0')<=9){
                u=10*u+(s[idx]-'0');
            }else{
                break;
            }
            idx++;
        }

        if(s[idx]=='<')o=-1,idx+=2;
        else if(s[idx]=='*') o=0,idx++;
        else if(s[idx]=='>')o=1,idx+=2;

        for(;;){
            if(0<=(s[idx]-'0') and (s[idx]-'0')<=9){
                v=10*v+(s[idx]-'0');
            }else{
                break;
            }
            idx++;
        }
        if(s[idx]=='+') pl=1;
        idx++;
        for(;idx<s.size();){
            w=w*10+(s[idx]-'0');
            idx++;
        }

        u--,v--;
        if(o==1) swap(u,v);
        if(o!=0 and pl==0){
            es.push_back(edge<int>(v,u,0));
            es.push_back(edge<int>(u,v,w));
        }
        if(o!=0 and pl==1){
            es.push_back(edge<int>(v,u,0));
            es.push_back(edge<int>(v,u,-w));
        }
        if(o==0){
            undif.push_back(make_tuple(u,v,w,pl));
        }
    }

    int M=undif.size(),ans=-1;
    for(int bit=0;bit<(1<<M);bit++){
        rep(i,M){
            int u=get<0>(undif[i]),v=get<1>(undif[i]),w=get<2>(undif[i]),pl=get<3>(undif[i]);
            if((bit>>i)&1) swap(u,v);
            es.push_back(edge<int>(v,u,0));
            if(pl==0){
                es.push_back(edge<int>(u,v,w));
            }else{
                es.push_back(edge<int>(v,u,-w));
            }
        }
        // cout<<"---------------"<<endl;
        // for(auto e:es){
        //     cout<<e.src<<" -> "<<e.to<<" : "<<e.cost<<endl;
        // }
        auto dis=BellmanFord(es,N,0);
        rep(i,2*M) es.pop_back();
        if(dis.empty() or *min_element(ALL(dis))<0) continue;
        chmax(ans,*max_element(ALL(dis)));
    }
    if(ans>INF) cout<<"inf"<<endl;
    else cout<<ans<<endl;
    return 0;
}