Problem Description

ROI has $n$ cities and $m$ rail lines. Each rail line runs in one direction. The $i$-th rail line passes through and stops at cities $v_{i,1}, v_{i,2}, \dots, v_{i,l_i+1}$ in order, where the track length from $v_{i,j} \to v_{i,j+1}$ is $t_{i,j}$.

If multiple rail lines pass through city $u$, then you can transfer to another rail line at city $u$. (For each rail line, you may get on or off at any stop.)

You need to find a path from city $1$ to city $n$ such that the total length is minimized, and subject to that, the sum of squares of the distances traveled on trains between every pair of adjacent transfer points along the path is maximized.

Note: both the start point and the end point are transfer points. The problem guarantees that a solution exists.

Input Format

The first line contains two integers $n, m$, meaning there are $n$ cities and $m$ rail lines.

The next $m$ lines describe the rail lines. Each line starts with an integer $l_i$ denoting the length of the rail line, 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}$, with meanings as described above. It is guaranteed that there are no repeated cities within a single rail line.

Output Format

Output one line with two integers. The first number is the shortest path length, and the second number is the maximum possible sum of squares.

2 1
1 1 3 2

3 9

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

9 35

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

10 82

Hint

Sample Explanation

For sample set #2:

Taking line $1$ directly from city $1$ to city $5$ is not the best plan (it cannot achieve the shortest time). The best plan is:

Take line $1$ from city $1$ to city $2$.

Transfer to line $2$ and ride to city $3$.

Transfer back to line $1$ and ride to city $5$.

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

For sample set #3:

No matter at which station you transfer to line $2$ on the way, the result is the same. The sum of squares is $1^2 + 9^2 = 82$.

Constraints

Note: This problem provides only part of the testdata. For the full testdata, please go to LOJ P2769 for judging.

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

Translated by ChatGPT 5