Alice 和 Bob 在一个有向图 $G$ 上玩游戏。$G$ 中有 $n$ 个顶点，编号为 $1, 2, \dots, n$。最初，$G$ 中没有边。Alice 首先会从商店购买一些有向边，并将它们添加到 $G$ 中。之后，Bob 需要删除边，直到 $G$ 中没有边为止。在每一轮删除中，Bob 可以从 $G$ 中删除一个边集 $S$，使得仅保留 $S$ 中的边时，该图是无环的。注意，Alice 可以什么都不买，在这种情况下，删除轮数为 0。

商店里有 $m$ 条边。Alice 有 $c$ 美元，因此她购买边的总价格不能超过 $c$。Alice 希望最大化删除轮数，而 Bob 希望最小化删除轮数。Alice 和 Bob 都会采取最优策略。请编写一个程序来预测删除轮数。

输入格式

输入仅包含一组测试数据。

第一行包含三个整数 $n, m$ 和 $c$ ($2 \le n \le 2\,000, 1 \le m \le 5\,000, 1 \le c \le 10^9$)，分别表示 $G$ 中的顶点数、商店中的边数以及 Alice 拥有的美元数量。

接下来的 $m$ 行中，第 $i$ 行 ($1 \le i \le m$) 包含三个整数 $u_i, v_i$ 和 $p_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le p_i \le 100\,000$)，表示商店中的一条有向边。Alice 可以支付 $p_i$ 美元购买该边，并在 $G$ 中添加一条从顶点 $u_i$ 到顶点 $v_i$ 的边。

输出格式

输出一行，包含一个整数，表示删除轮数。

样例

样例输入 1

3 2 4
1 2 5
2 3 6

样例输出 1

0

样例输入 2

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

样例输出 2

1