題目描述

這是一道模板題。

給定一個圖，每條邊有容量和費用，使用每條邊的單位流量需要支付特定的費用。給定源點 $1$ 和匯點 $n$，求圖的最大流和最大流需要支付的最小費用。

輸入格式

第一行兩個整數 $n$、$m$，表示有 $n$ 個點 $m$ 條邊。

從第二行開始的之後 $m$ 行，每行四個整數 $s_i$、$t_i$、$c_i$、$w_i$ 表示一條從 $s_i$ 到 $t_i$ 的邊，容量為 $c_i$，單位流量需要支付的費用為 $w_i$。

輸出格式

一行兩個整數，分別表示最大流和最大流需要支付的最小費用。

範例輸入

8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0

範例輸出

6 24

數據範圍與提示

• $1 \leq n \leq 400, 0 \leq m \leq 15000, w_i \geq 0$
• 保證輸入數據、中間結果以及答案在 32 位有符號整數範圍內。