Problem: Background

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves drawing as much as programming. So far, Yu-kun has drawn many pictures with circles and arrows. The arrows are always drawn to connect the circles. One day Yu finds out that these pictures are graphs.

It seems that circles are called vertices and arrows are called edges. Furthermore, when drawing an arrow, Yu always wrote one positive integer on it. A graph consisting of directed edges with weights in this way is called a weighted directed graph.

Today Yu-kun learned a new word, the cycle of the cycle. A cycle is a sequence of connected edges in which all vertices appear at most once, and the first and last vertices are the same. If the sum of the weights of the edges of a cycle is negative, then such a cycle is called a negative cycle.

Yu-kun, who knew a lot of new words, came up with a problem.

Problem

A weighted directed graph with no cycle is given. Select two different vertices i and j and add one directed edge with weight w (w <0) from i to j. Find i and j in the graph that create a negative cycle, and find the maximum sum of the weights of the sides that belong to that negative cycle. If such i, j does not exist, output "NA".

Constraints

The input satisfies the following conditions.

* 2 ≤ V ≤ 100000
* 1 ≤ E ≤ 500000
* -100 ≤ w <0
* 0 ≤ ci ≤ 100 (0 ≤ i ≤ E-1)
* 0 ≤ si, ti ≤ V-1 (0 ≤ i ≤ E-1)
* The same si and ti pair never appears while typing
* si and ti are different

Input


V E w
s0 t0 c0
s1 t1 c1
...
s (E-1) t (E-1) c (E-1)


The number of vertices V, the number of edges E, and the weight w of the edge to be added are given in the first line, separated by blanks.

The information of the directed edge is given as si ti ci in the following E line. (0 ≤ i ≤ E-1)

This means that there is a directed edge of the weight ci from si to ti.

Output

Output the maximum value of the sum of the weights of the sides belonging to the negative cycle, which can be created by adding the directed side of the weight w, to one line. If a negative cycle cannot be created no matter where you add an edge, output "NA".

Examples

Input

3 2 -3
0 1 1
0 2 5


Output

-2


Input

3 2 -1
0 1 1
0 2 5


Output

NA


Input

7 8 -8
0 1 5
0 4 3
1 2 10
1 3 1
3 6 6
4 3 1
4 5 2
4 6 2


Output

-1


Input

5 4 -30
0 1 1
1 3 15
1 4 4
2 1 3


Output

-12

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 100005

struct Edge{
	Edge(int arg_to,int arg_weight){
		to = arg_to;
		weight = arg_weight;
	}
	int to,weight;
};

int V,E,W;
int maximum;
int in_num[SIZE];
bool dp[SIZE][105];
vector<Edge> G[SIZE];

//https://betrue12.hateblo.jp/entry/2020/08/09/150101

int main(){

	scanf("%d %d %d",&V,&E,&W);

	int abs_W = -W;

	for(int i = 0; i < V; i++){

		//dp[終端ノード][重みの総和] := 存在するならtrue
		dp[i][0] = true;
		for(int k = 1; k <= abs_W-1; k++){
			dp[i][k] = false;
		}
	}
	for(int i = 0; i < V; i++){

		in_num[i] = 0;
	}

	int from,to,cost;

	for(int i = 0; i < E; i++){

		scanf("%d %d %d",&from,&to,&cost);
		G[from].push_back(Edge(to,cost));
		in_num[to]++;
	}

	queue<int> Q;
	for(int i = 0; i < V; i++){

		if(in_num[i] == 0){

			Q.push(i);
		}
	}

	int maximum = -BIG_NUM;

	while(!Q.empty()){

		int node_id = Q.front();
		Q.pop();

		for(int i = 0; i <= abs_W-1; i++){

			if(!dp[node_id][i])continue;

			for(int k = 0; k < G[node_id].size(); k++){

				int next_node = G[node_id][k].to;
				int next_cost = i+G[node_id][k].weight;

				if(next_cost >= abs_W)continue;

				maximum = max(maximum,next_cost+W);
				dp[next_node][next_cost] = true;
			}
		}

		for(int i = 0; i < G[node_id].size(); i++){

			int next = G[node_id][i].to;
			in_num[next]--;
			if(in_num[next] == 0){

				Q.push(next);
			}
		}
	}

	if(maximum == -BIG_NUM){

		printf("NA\n");
	}else{

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


	return 0;
}