Description

When the Wenchuan earthquake struck, Sichuan ** High School was in class. As soon as the earthquake occurred, the teachers immediately led $x$ students to evacuate. The whole school can be abstracted as a directed graph with $n$ nodes and $m$ edges. Node $1$ is the classroom, and node $n$ is the safe zone. Each edge can only accommodate a certain number of students; if exceeded, the building would collapse. Due to the large number of people, the principal decided to evacuate in several batches. Only after the first batch has completely evacuated may the second batch start from node $1$. Please help the principal calculate the maximum number of students that can be transported in each batch, and how many batches are needed to transport all $x$ students.

Input Format

The first line contains three integers $n, m, x$.
The next $m$ lines each contain three integers $a, b, c$ ($1 \le a, b \le n$, $0 \le c \le x$), describing an edge: there is an edge from node $a$ to node $b$ that can accommodate $c$ students.

Output Format

If it is impossible to reach the destination (node $n$), output Orz Ni Jinan Saint Cow!. Otherwise, output two integers: the maximum number of students that can be transported in each batch, and the number of batches needed to transport all $x$ students.

6 7 7
1 2 1
1 4 2
2 3 1
4 5 1
4 3 1
3 6 2
5 6 1

3 3

Hint

[Note]

For example, consider the graph

1 2 100
2 3 1

$100$ students first rush to node $2$, and then go along edge $2 \to 3$ one by one.

According to the 2018 "Shen Niu" rules, this is not allowed.

In other words, each batch of students must depart from the source simultaneously and arrive at the sink simultaneously.

[Constraints]

For $100\%$ of the testdata, $0 \le x < 2^{31}$, $2 \le n \le 200$, $1 \le m \le 2000$.

Translated by ChatGPT 5