최소 비용 최대 유량

문제

$N$개의 정점과 $E$개의 단방향 간선으로 이루어진 네트워크가 주어진다. 각 간선은 보낼 수 있는 최대 유량과 유량 1당 발생하는 비용을 가진다. 정점 1에서 정점 $N$까지 보낼 수 있는 최대 유량과, 최대 유량을 흘릴 때 발생하는 최소 비용을 구하라.

여러 경로를 통해 유량을 흘릴 수 있으며, 각 간선에 흐르는 유량에 해당 간선의 비용을 곱한 값을 모두 합한 것이 총 비용이 된다.