Minimum Cost Maximum Flow

Problem Description

Given a graph where each edge has a capacity and a cost (using one unit of flow on an edge requires paying a specific cost). Given a source vertex $1$ and a sink vertex $n$, find the maximum flow of the graph and the minimum cost required to achieve that maximum flow.

Input Format

The first line contains two integers $n, m(1\leq n\leq 400, 0\leq m\leq 15000)$, meaning there are $n$ vertices and $m$ edges.

The following $m$ lines, starting from the second line, each contain four integers $u, v, c, w$, representing a directed edge from $u$ to $v$ with capacity $c$ and unit-flow cost $w$.

All input numbers are guaranteed not to exceed $2^{31}-1$; the final flow is guaranteed not to exceed $5000$, and the minimum cost is guaranteed not to exceed $10^9$.

Output Format

One line with two integers: the maximum flow and the minimum cost required to achieve that maximum flow.

Sample Input

8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0

Sample Output

6 24

Constraints

$1\leq n\leq 400$, $0\leq m\leq 15000$; all values $\leq 2^{31}-1$; final flow $\leq 5000$; minimum cost $\leq 10^9$.

Hint

• Use the successive shortest path (SPFA / Dijkstra with potentials) algorithm for minimum-cost maximum-flow: repeatedly find the shortest-cost augmenting path and push as much flow as possible until no more augmenting path exists.