Minimum Cost Maximum Flow

Given a directed graph (network) \(G=(V,E)\) with \(n\) nodes and \(m\) edges, where the nodes are numbered \(1\) through \(n\) and the edges are numbered \(1\) through \(m\). The network has a source node \(s\) and a sink node \(t\). Each edge \((u,v)\) is associated with a capacity \(w(u,v)\) and a cost per unit flow \(c(u,v)\).

Your task is to determine a flow \(f(u,v)\) for every edge that satisfies the following conditions:

1. \(0 \le f(u,v) \le w(u,v)\): The flow on any edge cannot exceed its capacity.
2. For every node \(p \in V \setminus \{s,t\}\), \(\sum_{(i,p)\in E} f(i,p) = \sum_{(p,i)\in E} f(p,i)\): The total flow into any node (other than \(s\) and \(t\)) equals the total flow leaving that node.
3. \(\sum_{(s,i)\in E} f(s,i) = \sum_{(i,t)\in E} f(i,t)\): The total flow leaving the source equals the total flow entering the sink.

Define the value of the flow as \(F(G)=\sum_{(s,i)\in E} f(s,i)\) and the total cost as \(C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)\). The goal is to compute the minimum cost maximum flow: first maximize \(F(G)\) and then, among all flows that achieve this maximum, choose one that minimizes \(C(G)\).

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), and \(t\) representing the number of nodes, the number of edges, the source node, and the sink node respectively. The next \(m\) lines each contain four integers \(u\), \(v\), \(w\), and \(c\) denoting a directed edge from node \(u\) to node \(v\) with a capacity of \(w\) and a cost of \(c\) per unit flow.

outputFormat

Output two space-separated integers: the maximum possible flow from \(s\) to \(t\) and the minimum cost to achieve that flow.

sample

2 1 1 2
1 2 5 2

5 10