Description

Given a directed graph, each edge has a capacity $c$ and an expansion cost $w$. The expansion cost is the cost required to increase the capacity by $1$. Find:

1. The maximum flow from $1$ to $n$ without any expansion.
2. The minimum total expansion cost required to increase the maximum flow from $1$ to $n$ by $k$.

Input Format

The first line contains three integers $n, m, k$, denoting the number of vertices, the number of edges, and the required increase in flow.

The next $m$ lines each contain four integers $u, v, c, w$, describing a directed edge from $u$ to $v$ with capacity $c$ and expansion cost $w$.

Output Format

Output one line containing two integers, which are the answers to problems $1$ and $2$ respectively.

5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1

13 19

Hint

• Constraints
  • For $30\%$ of the testdata, it is guaranteed that $n \le 100$.
  • For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^3$, $1 \le m \le 5 \times 10^3$, $1 \le k \le 10$, $1 \le u, v \le n$, and $1 \le c, w \le 100$.

Translated by ChatGPT 5