최소 비용 최대 유량

정점이 $1$번부터 $N$번까지 번호가 붙은 방향 네트워크가 주어진다. 모든 간선은 번호가 작은 정점에서 번호가 큰 정점으로 향한다. $1$번 정점에서 $N$번 정점으로 보낼 수 있는 최대 유량 $F$와, 그 최대 유량을 보내는 방법 중 비용 합의 최솟값 $C$를 출력하여라.

간선 하나에 유량 $x$를 흘리면 그 간선의 비용은 $x \cdot cost_i$만큼 더해진다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1\ cap_1\ cost_1$ $u_2\ v_2\ cap_2\ cost_2$ $\vdots$ $u_M\ v_M\ cap_M\ cost_M$

첫째 줄에 $F$와 $C$를 공백으로 구분하여 출력한다.

• $2 \leq N \leq 300$.
• $0 \leq M \leq 5\ 000$.
• $1 \leq u_i < v_i \leq N$ ($1 \leq i \leq M$).
• $0 \leq cap_i \leq 10^6$ ($1 \leq i \leq M$).
• $-10^6 \leq cost_i \leq 10^6$ ($1 \leq i \leq M$).