This is a template problem.

Given a graph where each edge has a capacity and a cost, a specific cost must be paid for each unit of flow through the edge. Given a source $1$ and a sink $n$, find the maximum flow and the minimum cost required to achieve that maximum flow.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of edges, respectively.

Each of the following $m$ lines contains four integers $s_i$, $t_i$, $c_i$, and $w_i$, representing an edge from $s_i$ to $t_i$ with capacity $c_i$ and a cost of $w_i$ per unit of flow.

Output

A single line containing two integers, representing the maximum flow and the minimum cost to achieve that maximum flow, respectively.

Examples

Input 1

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

Output 1

6 24

Note

$1 \leq n \leq 400, 0 \leq m \leq 15000, w_i \geq 0$. It is guaranteed that the input data, intermediate results, and the answer fit within the range of a 32-bit signed integer.