Alice and Bob are playing a game on a directed graph $G$. There are $n$ vertices in $G$, labeled by $1,2,…,n$. 
Initially, there are no edges in $G$. Alice will first buy some direct edges from the shop and then add them into $G$. After that, Bob needs to delete edges until there are no edges in $G$. In a deletion round, Bob can delete a subset of edges $S$ from $G$, such that when only keeping edges in $S$, the graph is acyclic. Note that Alice can buy nothing, and in such a case the number of deletion rounds is $0$.
There are $m$ edges in the shop. Alice has $c$ dollars, so the total price of edges she will buy should not exceed $c$. Alice wants to maximize the number of deletion rounds while Bob wants to minimize it. Both Alice and Bob will play optimally. Please write a program to predict the number of deletion rounds.

The input contains only a single case.
The first line of the input contains three integers $n,m, c\ (2≤n≤2000,\ 1≤m≤5000,\ 1≤c≤10^9)$, denoting the number of vertices in $G$, the number of edges in the shop, and how many dollars Alice has.
In the next $m$ lines, the $i$-th line $(1≤i≤m)$ contains three integers $u_i,v_i, p_i\ (1≤u_i,v_i≤n,\ u_i≠v_i,\ 1≤p_i≤100000)$, denoting a directed edge in the shop. Alice can pay $p_i$ dollars to buy it, and add an edge from vertex $u_i$ to vertex $v_i$ in $G$.

Print a single line containing an integer, denoting the number of deletion rounds.