kun Likes a Directed Graph

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

inputFormat

outputFormat

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

样例

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

-1