Input
The first line of input contains a line contains a line with
four non-negative integers, $2
\le n \le 250$, $0 \le m
\le 5\, 000$, $0 \le s \le
n-1$ and $0 \le t \le
n-1$, separated by single spaces, where $n$ is the numbers of nodes in the
graph, $m$ is the number
of edges, $s$ is the
source and $t$ is the sink
($s \ne t$). Nodes are
numbered from $0$ to
$n-1$. Then follow
$m$ lines, each line
consisting of four (space-separated) integers $u$, $v$, $c$ and $w$ indicating that there is an edge
from $u$ to $v$ in the graph with capacity
$1 \le c \le 10\, 000$ and
cost $1 \le w \le 1\,
000$.
Output
Output a single line containing two integers; the size
$F$ of a maximum flow from
node $s$ to node
$t$, and the cost of a
mimimum cost flow of size $F$. You may assume that $F < 2^{31}$.
| Sample Input 1 |
Sample Output 1 |
4 4 0 3
0 1 4 10
1 2 2 10
0 2 4 30
2 3 4 10
|
4 140
|
| Sample Input 2 |
Sample Output 2 |
2 1 0 1
0 1 1000 100
|
1000 100000
|
| Sample Input 3 |
Sample Output 3 |
2 1 1 0
0 1 1000 100
|
0 0
|
