Description

Given a directed graph (hereinafter referred to as a network) $G=(V,E)$ with $n$ vertices and $m$ edges. The vertices are numbered $1 \sim n$, and the edges are numbered $1 \sim m$. The source of the network is $s$, and the sink is $t$. Each edge $(u,v)$ has a capacity limit $w(u,v)$ and a unit cost $c(u,v)$.

You need to assign a flow $f(u,v)$ to each edge $(u,v)$ such that:

1. $0 \leq f(u,v) \leq w(u,v)$ (the flow on each edge does not exceed its capacity limit);
2. $\forall p \in \{V \setminus \{s,t\}\}$, $\sum_{(i,p) \in E} f(i,p) = \sum_{(p,i) \in E} f(p,i)$ (for all vertices except the source and the sink, the total inflow equals the total outflow);
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 network flow $F(G)=\sum_{(s,i)\in E} f(s,i)$ and the network cost $C(G)=\sum_{(i,j)\in E} f(i,j) \times c(i,j)$.

You need to find the minimum-cost maximum flow of the network, that is, maximize $F(G)$ and, subject to that, minimize $C(G)$.

Input Format

The first line contains four integers $n,m,s,t$, representing the number of vertices, the number of edges, the index of the source, and the index of the sink, respectively.

Each of the next $m$ lines contains four integers $u_i,v_i,w_i,c_i$, representing the start vertex, end vertex, capacity limit, and unit cost of the $i$-th edge.

Output Format

Output two integers: the maximum flow $F(G)$ and, subject to $F(G)$ being maximum, the minimum cost $C(G)$.

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

Hint

Constraints:

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^3$, $1 \leq m \leq 5 \times 10^4$, $1 \leq s,t \leq n$, $u_i \neq v_i$, $0 \leq w_i,c_i \leq 10^3$, and the network’s maximum flow and minimum cost $\leq 2^{31}-1$.

The testdata is randomly generated.

Translated by ChatGPT 5