Problem Description

In the country of ROI, there are $n$ cities and $m$ railways, each of which operates unidirectionally. The $i$-th railway passes through cities $v_{i,1}, v_{i,2}, \dots, v_{i,l_i+1}$ and stops there, with the railway length from $v_{i,j}$ to $v_{i,j+1}$ being $t_{i,j}$.

If multiple railways pass through city $u$, you can transfer to other railways at city $u$. (You can board or alight at any stop on each railway.)

You need to find a path from city $1$ to city $n$ that minimizes the total length, and under this condition, maximizes the sum of the squares of the distances on the train between adjacent transfer points.

Note: Both the starting and ending points are considered transfer points, and the problem guarantees a solution exists.

Input Format

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

The next $m$ lines, each starting with an integer $l_i$ indicating the length of the railway, followed by $2l_i+1$ integers in the form $v_{i,1}, t_{i,1}, v_{i,2}, \dots, v_{i,l_i}, t_{i,l_i}, v_{i,l_i+1}$, as described in the problem.

Output Format

A single line containing two integers: the first number represents the shortest path length, and the second number represents the maximum sum of squares.

Sample Input and Output

Input Sample #1

2 1
1 1 3 2

Output Sample #1

3 9

Input Sample #2

5 2
4 1 3 2 3 3 5 5 10 4
3 4 2 2 1 3 4 1

Output Sample #2

9 35

Input Sample #3

5 2
3 1 1 2 2 3 3 4
3 2 2 3 3 4 4 5

Output Sample #3

10 82

Notes/Hints

Sample Explanation

For Sample Set #2:

Directly taking the 1st line from city 1 to city 5 is not the optimal solution (it does not achieve the shortest time). The optimal solution is:

• Take the 1st line from city 1 to city 2;
• Transfer to the 2nd line, travel to city 3;
• Then transfer back to the 1st line, travel to city 5.

In this case, the sum of squares is $3^2 + 1^2 + 5^2 = 35$.

For Sample Set #3:

Regardless of where you transfer to the 2nd line, the result is the same. The sum of squares is $1^2 + 9^2 = 81$.

Data Range

Note: Only partial data is provided; for complete data, please refer to LOJ P2769 for evaluation.

For all data: $1 \le m \le 10^6$, $1 \le v_{i,j} \le n$, $1 \le t_{i,j} \le 1000$, where $= \sum l_i$.

见题面 Input 部分

见题面 Output 部分