Minimum Cost Maximum Flow with Negative Cycle Augmentation

You are given a directed flow network with n vertices and m edges. Each edge is associated with a capacity and a cost. The source is s and the sink is t.

Your task is to compute the maximum flow from s to t and, among all flows achieving that value, find the one with the minimum total cost. In this problem, negative cost edges and cycles with a total negative cost are allowed. In particular, you are permitted to add a unit of flow circulating through a cycle that does not pass through s or t (i.e. a cycle entirely in the subgraph of V\{s,t}). Such circulation may be used to further reduce the overall cost.

The network is given in the following format. All formulas are given in \(\LaTeX\) format, e.g. \(n\) denotes the number of nodes.

inputFormat

The input begins with a line containing four integers \(n\), \(m\), \(s\), and \(t\) (\(1 \leq s,t \leq n\)). Then follow \(m\) lines. Each of these lines contains four integers \(u\), \(v\), \(\text{capacity}\), and \(\text{cost}\) representing a directed edge from node \(u\) to node \(v\) with the given capacity and cost.

outputFormat

Output two integers in one line separated by a space: the maximum flow from \(s\) to \(t\) and the corresponding minimum total cost (taking advantage of permissible negative cycles).

sample

4 5 1 4
1 2 3 1
1 3 2 2
2 3 2 -2
2 4 2 2
3 4 3 1

4 6