Optimal Railway Transfer

ROI nation has n cities and m unidirectional railway lines. The i-th railway goes through cities \(v_{i,1},v_{i,2},\dots,v_{i,l_i+1}\) in that order, with a segment from \(v_{i,j}\) to \(v_{i,j+1}\) having length \(t_{i,j}\) (in latex: \(t_{i,j}\)). At any stop, you may board or deboard the train. Moreover, if a city is visited by at least two different railways, you are allowed to switch (transfer) trains at that city. Note that the starting city (city 1) and the destination (city n) are always considered transfer points.

Your task is to choose a path from city 1 to city n that satisfies the following two criteria in lexicographical order:

1. The total distance traveled is minimized.
2. Among all paths with minimal total distance, the sum of the squares of the "on‐train" ride lengths between consecutive transfer points is maximized. That is, if a path consists of consecutive train rides with distances \(d_1,d_2,\dots,d_k\), you want to maximize \(\sum_{i=1}^{k} d_i^2\).

You are guaranteed that there exists at least one path from city 1 to city n satisfying the above.

Note on transfers: In each railway, you can only board and deboard at stops. However, you are allowed to deboard at an intermediate station even if that station is not a transfer point, but you can only change to another railway if the station is a transfer point (i.e. it is either city 1, city n, or is served by at least two different railways).

inputFormat

The input begins with a line containing two integers n and m \( (2 \le n \le 10^5,\ 1 \le m \le 10^5)\) representing the number of cities and the number of railway lines, respectively.

Then for each railway line, the input is given in the following format:

 l  vi,1 vi,2 ... vi,l+1
 ti,1 ti,2 ... ti,l

Here, l (\(l \ge 1\)) is the number of segments in this railway (so there are \(l+1\) stations on this railway), v_i,j are the cities (1-indexed) that the railway passes through in order, and t_i,j is the distance of the segment from v_i,j to v_i,j+1.

It is guaranteed that there is at least one valid path from city 1 to city n.

outputFormat

Output two integers separated by a space: the minimal total distance and the maximum sum of squares of the ride lengths between consecutive transfer points corresponding to a valid path achieving the minimal distance.

Format:

TotalDistance MaxSumSquares

sample

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

4 16