#322 Minimum Cost Maximum Flow

Statement

Statement language

You are given a directed network with vertices numbered from $1$ to $N$ . Find the maximum flow $F$ from vertex $1$ to vertex $N$ , and the minimum total cost $C$ among flows of value $F$ . Sending $x$ units through edge $i$ costs $x \cdot cost_i$ . Parallel edges, self-loops, and zero capacities or costs are allowed.

Input

The input is given in the following format:

$N\ M$ $u_1\ v_1\ cap_1\ cost_1$

Output

$F$ and $C$ must be printed on one line, separated by a space.

Constraints

$2 \leq N \leq 500$ .
$0 \leq M \leq 20\,000$ .
$1 \leq u_{i}, v_{i} \leq$ ().

Subtasks

#	Score	Constraints
1	20	$N \leq 30$ ; $M \leq 100$ ; $\sum_{i:u_i=1} cap_i \leq 50$ .

Samples

Input

Output

4 1352