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 expansion cost required to increase the maximum flow from 1 to $N$ by $K$.

Input

The first line of the input contains three integers $N, M, K$, representing the number of vertices, the number of edges, and the required increase in flow, respectively.

Each of the following $M$ lines contains four integers $u, v, C, W$, representing an edge from $u$ to $v$ with capacity $C$ and expansion cost $W$.

Output

The output contains two integers on a single line, representing the answers to problem 1 and problem 2, respectively.

Examples

Input 1

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

Output 1

13 19

Constraints

• For 30% of the data, $N \le 100$.
• For 100% of the data, $N \le 1000$, $M \le 5000$, $K \le 10$.