Description

Alice and Bob are learning about maximum flow and minimum cost maximum flow in their graph theory course.

Maximum Flow Problem: Given a directed graph representing a transportation network, a source $S$, and a sink $T$, each edge has a maximum capacity. A valid network flow must satisfy: (1) the actual flow on each edge is non-negative and does not exceed its maximum capacity; (2) for all nodes except the source $S$ and the sink $T$, the total inflow equals the total outflow; the net outflow from $S$ equals the net inflow to $T$, which is the total transport volume of the network flow scheme. The maximum flow problem is to find a network flow scheme with the maximum total transport volume for a given transportation network.

The figure below illustrates a maximum flow problem. For each edge, the number on the right represents the maximum capacity of that edge, and the number on the left represents the actual flow on that edge in an optimal solution. Note that the solution to a maximum flow problem may not be unique.

For a given transportation network, Alice first determines a maximum flow. If there are multiple solutions, Alice can choose any one of them. Afterward, Bob assigns a unit cost to each edge (the unit cost must be a non-negative real number), such that the sum of the unit costs of all edges equals $P$. The total cost is equal to the actual flow of each edge multiplied by its unit cost. Note that Bob knows the maximum flow scheme chosen by Alice before he assigns the unit costs.

Now, Alice wants to minimize the total cost, while Bob wants to maximize the total cost. We want to know the value of the maximum flow and the total cost if both parties play optimally.

Input

The first line contains three integers $N$, $M$, and $P$. $N$ represents the number of nodes in the given transportation network, $M$ represents the number of directed edges, and the meaning of $P$ is described in the problem description. To simplify the problem, we assume the source $S$ is node $1$ and the sink $T$ is node $N$.

The next $M$ lines each contain three integers $A$, $B$, and $C$, representing a directed edge from node $A$ to node $B$ with a maximum capacity of $C$.

Output

The first line contains an integer representing the value of the maximum flow. The second line contains a real number representing the total cost. It is recommended that contestants output at least four decimal places.

Examples

Input 1

3 2 1
1 2 10
2 3 15

Output 1

10
10.0000

Note 1

For Alice, the maximum flow scheme is fixed. The actual flow on both edges is $10$. For Bob, he assigns a cost of $0.5$ to the first edge and $0.5$ to the second edge. The total cost is: $10 \times 0.5 + 10 \times 0.5 = 10$. It can be proven that there is no assignment scheme with a higher total cost.

Constraints

• For 20% of the test data: the maximum capacity of all directed edges is $1$.
• For 100% of the test data: $N \le 100$, $M \le 1000$.
• For 100% of the test data: all node labels are in the range $1..N$. $1 \le$ maximum capacity of each edge $\le 50000$. $1 \le P \le 10$. There are no edges with the same start and end nodes in the given transportation network.

For each test case, if the first line of the output file matches the standard output, you receive 30% of the points for that test case. If the second line of the output file has an error of less than $0.001$ compared to the standard output, you receive 70% of the points for that test case. These two parts are cumulative.

This problem uses a custom checker. To prevent errors in the custom checker, even if you cannot correctly determine the answer to a question, you should still output a number in the corresponding position.