408989: GYM103409 E Buy and Delete

Alice and Bob are playing a game on a directed graph $$$G$$$. There are $$$n$$$ vertices in $$$G$$$, labeled by $$$1,2,\dots,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$$$ and $$$c$$$ ($$$2 \leq n\leq 2\,000$$$, $$$1\leq m \leq 5\,000$$$, $$$1\leq c\leq 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 \le i \le m)$$$ contains three integers $$$u_i,v_i$$$ and $$$p_i$$$ ($$$1\leq u_i,v_i\leq n$$$, $$$u_i\neq v_i$$$, $$$1\leq p_i\leq 100\,000$$$), 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.

3 2 4
1 2 5
2 3 6

0

3 3 3
1 2 1
2 3 1
1 3 1

1