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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100

enum Type{
	From_front,
	From_back,
	Undefined,
};

enum Which{
	Ijyou,
	Inai,
};

struct Info{
	int from,to,dist;
	Type type;
	Which which;
};

struct Edge{
	void set(int arg_from,int arg_to,int arg_dist){
		from = arg_from;
		to = arg_to;
		dist = arg_dist;
	}
	int from,to,dist;
};

int N,num_constraint;
int POW[7];
int min_dist[NUM];
Info info[2*NUM];
Edge edge[4*NUM];

bool BellmanFord(int E){

	bool FLG = true,updated;

	for(int i = 0; i < N; i++)min_dist[i] = BIG_NUM;
	min_dist[0] = 0;

	for(int i = 0; i < N; i++){
		updated = false;
		for(int k = 0; k < E; k++){
			if(min_dist[edge[k].from] != BIG_NUM && min_dist[edge[k].to] > min_dist[edge[k].from] + edge[k].dist){
				min_dist[edge[k].to] = min_dist[edge[k].from] + edge[k].dist;

				updated = true;
				if(i == N-1){ //★★負閉路あり★★
					FLG = false;
					break;
				}
			}
		}
		if(!updated)break;
		if(!FLG)break;
	}

	return FLG;
}


bool is_num(char ch){
	return ch >= '0' && ch <= '9';
}

int main(){

	for(int i = 0; i < 7; i++)POW[i] = pow(2,i);

	scanf("%d %d",&N,&num_constraint);

	int num_undefined = 0;
	vector<int> UNDEFIND;

	char buf[50];

	int tmp,index;
	bool FLG;

	int edge_index = 0;

	for(int i = 0; i < num_constraint; i++){
		scanf("%s",buf);

		tmp = 0;
		index = 0;

		//fromの取得
		while(is_num(buf[index])){
			tmp = 10*tmp+buf[index]-'0';
			index++;
		}
		info[i].from = tmp-1;

		FLG = true;

		switch(buf[index]){
		case '>':
			info[i].type = From_back;
			index += 2;
			break;
		case '*':
			FLG = false;
			info[i].type = Undefined;
			num_undefined++;
			UNDEFIND.push_back(i);
			index += 1;
			break;
		case '<':
			info[i].type = From_front;
			index += 2;
			break;
		}

		//toの取得
		tmp = 0;
		while(is_num(buf[index])){
			tmp = 10*tmp+buf[index]-'0';
			index++;
		}
		info[i].to = tmp-1;

		if(buf[index] == '+'){
			info[i].which = Ijyou;
		}else{
			info[i].which = Inai;
		}
		index++;

		//distの取得
		tmp = 0;
		while(is_num(buf[index])){
			tmp = 10*tmp+buf[index]-'0';
			index++;
		}
		info[i].dist = tmp;

		if(!FLG)continue; //前後関係を決定できないなら、まだ辺は張らない

		/*★不等式を満たすように辺を張る★*/
		if(info[i].type == From_front){

			edge[edge_index++].set(info[i].to,info[i].from,0);

			if(info[i].which == Inai){

				edge[edge_index++].set(info[i].from,info[i].to,info[i].dist);

			}else{

				edge[edge_index++].set(info[i].to,info[i].from,-info[i].dist);
			}

		}else{ //info[i].type == From_back

			edge[edge_index++].set(info[i].from,info[i].to,0);

			if(info[i].which == Inai){

				edge[edge_index++].set(info[i].to,info[i].from,info[i].dist);

			}else{

				edge[edge_index++].set(info[i].from,info[i].to,-info[i].dist);
			}
		}
	}

	int ans = -1;
	int num_default = edge_index,tmp_E;
	int max_dist;

	//辺の前後関係を全通り試す
	for(int state = 0; state < POW[num_undefined];state++){

		tmp_E = num_default;

		for(int loop = 0; loop < num_undefined; loop++){
			if(state & (1 << loop)){ //From_Front

				edge[tmp_E++].set(info[UNDEFIND[loop]].to,info[UNDEFIND[loop]].from,0);

				if(info[UNDEFIND[loop]].which == Inai){

					edge[tmp_E++].set(info[UNDEFIND[loop]].from,info[UNDEFIND[loop]].to,info[UNDEFIND[loop]].dist);

				}else{

					edge[tmp_E++].set(info[UNDEFIND[loop]].to,info[UNDEFIND[loop]].from,-info[UNDEFIND[loop]].dist);

				}

			}else{ //From_back

				edge[tmp_E++].set(info[UNDEFIND[loop]].from,info[UNDEFIND[loop]].to,0);

				if(info[UNDEFIND[loop]].which == Inai){

					edge[tmp_E++].set(info[UNDEFIND[loop]].to,info[UNDEFIND[loop]].from,info[UNDEFIND[loop]].dist);

				}else{

					edge[tmp_E++].set(info[UNDEFIND[loop]].from,info[UNDEFIND[loop]].to,-info[UNDEFIND[loop]].dist);
				}

			}
		}

		if(!BellmanFord(tmp_E))continue;

		max_dist = 0;

		FLG = true;

		//最短距離の最大値を求める
		for(int i = 0; i < N; i++){
			max_dist= max(max_dist,min_dist[i]);
			if(min_dist[i] < 0){ //★1が先頭でないといけない★
				FLG = false;
				break;
			}
		}
		if(!FLG)continue;

		ans = max(ans,max_dist);
	}

	if(ans == BIG_NUM){

		printf("inf\n");

	}else{

		printf("%d\n",ans);
	}

	return 0;
}