School Escape Plan

During the Sichuan earthquake at Wenchuan, a school was in session at Sichuan **Middle School**. Immediately after the earthquake, the teachers led \(x\) students to escape. The school can be abstracted as a directed graph with \(n\) nodes and \(m\) directed edges. Node \(1\) is the classroom (start point) and node \(n\) is the safe zone (destination). Each edge has a capacity, meaning it can only allow a limited number of students at once; if this capacity is exceeded, the edge (or building) will collapse. Due to the excessive number of students, the principal decided to evacuate them in several batches. Only after the first batch of students has completely evacuated can the next batch start from node \(1\) to escape.

Your task is to determine two things:

1. The maximum number of students that can be evacuated in one batch. This is equivalent to the maximum flow from node 1 to node \(n\) in the given network.
2. The minimum number of batches needed to evacuate all \(x\) students. This is given by \(\lceil x / f \rceil\), where \(f\) is the maximum flow per batch.

It is guaranteed that \(n, m, x\) and the capacities of the edges are positive integers.

inputFormat

The first line contains three integers \(n\), \(m\), and \(x\), where \(n\) is the number of nodes, \(m\) is the number of edges, and \(x\) is the total number of students to evacuate.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(c\), representing a directed edge from node \(u\) to node \(v\) with capacity \(c\).

outputFormat

Output two integers separated by a space: the maximum number of students that can be evacuated in one batch, and the minimum number of batches needed to evacuate all \(x\) students.

sample

4 5 20
1 2 10
1 3 10
2 3 2
2 4 10
3 4 10

20 1