Problem Description

Given a cost flow network with $n$ nodes and $m$ edges, with source $s$ and sink $t$, find its maximum flow with minimum total cost.

Note that there are edges with negative cost and cycles whose total cost is negative.

Also note that in this problem, it is allowed to add a unit of flow to a cycle that does not pass through $s,t$ as a whole. In fact, if this situation is not allowed, then the Hamiltonian path problem can be reduced to this problem.

Input Format

The first line contains four positive integers $n,m,s,t$.

Lines $2$ to $m+1$ each contain four integers $x_i,y_i,f_i,v_i$, meaning that there is an edge from $x_i$ to $y_i$ with capacity $f_i$ and cost $v_i$.

Output Format

Output one line with two integers, representing the maximum flow and the minimum cost, respectively.

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

50 280

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

3 12

Hint

For $100\%$ of the testdata: $1\leq n\leq 200$, $1\leq m\leq {10}^{4}$, $0\leq f_i,|v_i|\leq 100$.

Note: It is not sure whether a cycle-canceling algorithm can pass. Since the testdata is graded in subtasks, even if it cannot pass, you should still be able to get some points.

Translated by ChatGPT 5