한국어 번역

문제 설명

이 문제는 템플릿 문제입니다.

각 간선마다 용량과 비용이 있는 그래프가 주어집니다. 각 간선에서 단위 유량을 사용할 때는 특정 비용을 지불해야 합니다. 소스 노드 $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비트 정수 범위 내에 있음이 보장됩니다.