Buy and Delete

Time limit2sMemory limit1024 MB

Summary

Alice buys directed edges with total price at most c so that Bob needs as many acyclic deletion rounds as possible to remove every edge.

Level: Hard8 of 10
Topics: Graph, Game theory, Combinatorics
Solved: No attempts yet

Problem

Alice and Bob are playing a game on a directed graph $G$ . $G$ has $n$ vertices labeled $1, 2, \dots, n$ . Initially, $G$ has no edges.

Alice first buys some directed edges from the shop and adds them to $G$ . After that, Bob deletes edges until $G$ has no edges. In each deletion round, Bob can delete a subset of edges $S$ from $G$ such that the graph that keeps only the edges in $S$ is acyclic. Alice can buy nothing, in which case the number of deletion rounds is $0$ .

The shop sells $m$ edges. Alice has $c$ dollars, so the total price of the edges she buys must not exceed $c$ . Alice wants to maximize the number of deletion rounds, and Bob wants to minimize it. Both play optimally. Predict the number of deletion rounds.

Input

The input contains only a single case.

The first line has three integers $n$ , $m$ , and $c$ ( $2 \le n \le 2000$ , $1 \le m \le 5000$ , $1 \le c \le 10^9$ ). Each of the next $m$ lines has three integers $u_i$ , $v_i$ , and $p_i$ ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ , $1 \le p_i \le 100000$ ). Line $i$ describes a shop edge from $u_i$ to $v_i$ that Alice can buy for $p_i$ dollars.

Output

Print a single integer, the number of deletion rounds.

Examples2

Example 1
Input
```
3 2 4
1 2 5
2 3 6
```
Expected output
```
0
```
Example 2
Input
```
3 3 3
1 2 1
2 3 1
1 3 1
```
Expected output
```
1
```