Optimal Maximum Flow Cost Minimization

Alice and Bob are playing a game on a transportation network. The network is represented as a directed graph with capacities on each edge, a source node \(S\) (node 1) and a sink node \(T\) (node \(n\)). A valid flow satisfies:

• For each edge, the flow is non-negative and does not exceed its capacity.
• For every vertex except \(S\) and \(T\), the total inflow equals the total outflow. The net flow out of \(S\) equals the net flow into \(T\), which is the total transported flow \(F\).

The maximum flow problem is to find the maximum possible \(F\) under these conditions.

Once Alice computes a maximum flow (if there are multiple valid solutions, she may choose any), Bob assigns a nonnegative real unit cost \(c_e\) to each edge so that \( \sum_e c_e = P \). The total cost is defined as \( \sum_e c_e f_e \), where \(f_e\) is the flow on edge \(e\). Since Bob sees Alice's flow assignment beforehand, his optimal strategy is to place the entire cost \(P\) on the edge carrying the highest flow, making the total cost \(P \times (\max_e f_e)\).

Knowing this, Alice will choose a maximum flow assignment that minimizes \( \max_e f_e \) while still achieving the maximum flow \(F\). In other words, if we let \(X\) denote the minimal possible value of \(\max_e f_e\) among all maximum flows, the final outcomes will be the maximum flow \(F\) and the total cost \(P \times X\).

A standard approach to solve this problem is:

1. Compute \(F\) using a standard maximum flow algorithm (e.g. Dinic's algorithm).
2. Perform a binary search on \(t\) (ranging from 0 to the maximum edge capacity). For each candidate \(t\), redefine each edge's capacity as \(\min(\text{original capacity}, t)\) and check whether the maximum flow remains \(F\). The smallest \(t\) for which this holds is \(X\).

Your task is to output \(F\) and \(P \times X\) given the graph and the value \(P\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(P\): the number of nodes, the number of edges, and the total cost to be distributed by Bob.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), describing a directed edge from node \(u\) to node \(v\) with capacity \(w\). Nodes are numbered from 1 to \(n\), where node 1 is the source \(S\) and node \(n\) is the sink \(T\).

outputFormat

Output two numbers separated by a space: the maximum flow \(F\) and the total cost, which is \(P \times X\), where \(X\) is the minimum possible value of \(\max_e f_e\) across all maximum flow assignments.

sample

4 5 10
1 2 6
1 3 4
2 3 2
2 4 4
3 4 5

8 40