MCMF

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.

각 간선에는 용량과 비용이 정해져 있다. 용량은 해당 간선으로 보낼 수 있는 유량의 최댓값이고, 비용은 유량을 1만큼 보낼 때 필요한 값이다.

시작 정점 $S$에서 도착 정점 $T$로 유량을 보내려고 한다.

각 간선으로 보내는 유량은 해당 간선의 용량을 넘을 수 없으며, $S$와 $T$를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다.

$S$에서 $T$로 보낼 수 있는 유량의 최댓값과, 해당 유량을 보낼 때 필요한 비용의 최솟값을 구하라.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 시작 정점 $S$, 도착 정점 $T$가 주어진다. $(2 \leq N \leq 100, 0 \leq M \leq \min(500, \frac{N(N-1)}{2}), 1 \leq S,T \leq N, S \neq T)$

두 번째 줄부터 $M$개의 줄에 걸쳐 방향 간선을 나타내는 네 정수 $u$, $v$, $c$, $w$가 주어진다. $(1 \leq u,v \leq N, u \neq v, 1 \leq c \leq 100, 0 \leq w \leq 1\,000\,000)$

이는 $u$번 정점에서 $v$번 정점으로 최대 $c$만큼의 유량을 보낼 수 있으며, 유량을 1만큼 보낼 때마다 $w$의 비용이 필요하다는 뜻이다.

같은 두 정점을 잇는 간선은 방향과 관계없이 두 번 이상 주어지지 않는다.

첫 번째 줄에 $S$에서 $T$로 보낼 수 있는 유량의 최댓값을 출력한다.

두 번째 줄에 해당 유량을 보낼 때 필요한 비용의 최솟값을 출력한다.