구매 후 삭제

Alice와 Bob은 방향 그래프 $G$에서 게임을 한다. $G$에는 $1, 2, \dots, n$번으로 번호가 붙은 $n$개의 정점이 있다. 처음에 $G$에는 간선이 없다.

Alice는 먼저 상점에서 방향 간선을 몇 개 사서 $G$에 추가한다. 그 뒤 Bob이 $G$에 간선이 남지 않을 때까지 간선을 삭제한다. 한 번의 삭제 라운드에서 Bob은 $G$의 간선 부분집합 $S$를 삭제할 수 있다. 이때 $S$의 간선만 남긴 그래프가 사이클이 없어야 한다. Alice는 아무것도 사지 않을 수 있으며, 이 경우 삭제 라운드 수는 $0$이다.

상점에는 $m$개의 간선이 있다. Alice가 가진 돈은 $c$달러이므로, 산 간선들의 가격 합은 $c$를 넘을 수 없다. Alice는 삭제 라운드 수를 최대화하려 하고, Bob은 이를 최소화하려 한다. 두 사람 모두 최적으로 행동한다. 삭제 라운드 수를 구하라.

입력은 한 개의 테스트 케이스로만 주어진다.

첫째 줄에 정수 $n$, $m$, $c$가 주어진다 ($2 \le n \le 2000$, $1 \le m \le 5000$, $1 \le c \le 10^9$). 이어지는 $m$개의 줄에는 정수 $u_i$, $v_i$, $p_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le p_i \le 100000$). $i$번째 줄은 Alice가 $p_i$달러를 내고 $u_i$에서 $v_i$로 가는 간선을 살 수 있음을 나타낸다.

삭제 라운드 수를 나타내는 정수 하나를 출력한다.