Đường đi dài nhất

Cho một đồ thị có hướng gồm \(n\) đỉnh được đánh chỉ số từ \(1\) đến \(n\) và \(m\) cạnh được
đánh chỉ số từ \(1\) đến \(m\), cạnh thứ \(i\) nối từ đỉnh \(u_{i}\) đến đỉnh \(v_{i}\) có trọng số \(w_{i}\).

Hãy tìm đường đi có nhiều cạnh nhất sao cho tổng trọng số của các cạnh thuộc đường đi này không vượt quá \(W\)

Input

Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(W\). \((1 \leq n \leq 100, 0 \leq m \leq n (n - 1), W \leq 10^{15})\).

Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa 3 số nguyên \(u_{i}\), \(v_{i}\) và \(w_{i}\). \((1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 10^9)\).

Output

Một dòng duy nhất chứa một số nguyên là số cạnh của đường đi tìm được.

Example

4 5 9
1 2 4
2 3 1
3 1 2
1 4 2
4 1 3

4

Scoring

Subtask \(1\) \((20\% test)\): \(W \leq 10^4\).

Subtask \(2\) \((40\% test)\): \(n \leq 10\).

Subtask \(3\) \((40\% test)\): không có ràng buộc gì thêm.