#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

An Jun is visiting a foreign city for the first time. He uses the city's train network to explore the city.
There are *N* train stations numbered 1 to *N*. Today, An Jun wants to travel from his hotel to
the city park, one of the city's most beautiful landmarks. The hotel is next to train station 1, and the city
park is next to train station *N*.

There are *M* train routes on the train network. The *i*th train route visits *S _{i}* + 1
cities numbered

*V*,

_{i1}*V*, ... ,

_{i2}*V*. Travelling between city

_{iSi + 1}*V*and city

_{i1}*V*takes

_{i2}*T*time, travelling between city

_{i1}*V*and city

_{i2}*V*takes

_{i3}*T*time, ... , travelling between city

_{i2}*V*and city

_{iSi}*V*takes

_{iSi + 1}*T*time for the

_{iSi}*i*th train route. An Jun can board a train and alight from a train at any part of its route, not necessarily at the first or last station. He can switch train routes any number of times, and board a train travelling on a certain train route more than once if necessary. An unlimited number of trains will travel on each train route, hence a train will be available regardless of when An Jun wants to board a train

An Jun wants his journey to fulfil 2 criterias. First, he must reach his destination in the shortest possible time.
Secondly, among all possible routes with the minimum possible amount of time, he wants the *effective quality* of his
trip to be maximised. When An Jun boards a train at a certain station and alights at another station, the *quality*
of the ride is defined as the square of the time spent travelling on the train. The *effective quality* of the trip is the sum of all the *qualities* of the train rides.

Help An Jun find both the shortest possible time required for him to reach the city park, and the highest *effective quality* that can be achieved.

## Input

The first line of input contains two integers *N* and *M*.

The next *M* lines of input contain the descriptions of the train routes.

The *i*th line begins with an integer *S _{i}*, followed by 2 ×

*S*+ 1 integers,

_{i}*V*,

_{i1}*T*,

_{i1}*V*,

_{i2}*T*, ... ,

_{i2}*V*,

_{iSi}*T*,

_{iSi}*V*

_{iSi + 1}## Output

Output two integers, the minimum amount of time required to get from city 1 to city *N*, and the highest possible
*effective quality*. It is guaranteed that there is at least one way to get from city 1 to city *N*.

## Limits

For all subtasks, 1 ≤*M*≤ 10

^{6}. 1 ≤

*T*≤ 1000. 1 ≤

_{ij}*S*≤ 10

_{i}^{6}. ∑

*S*≤ 10

_{i}^{6}.

Subtask 1 (10%): 2 ≤ *N _{i}* ≤ 10. ∑

*S*≤ 20.

_{i}*S*= 1.

_{i}Subtask 2 (10%): 2 ≤ *N _{i}* ≤ 1000. ∑

*S*≤ 1000.

_{i}*S*= 1.

_{i}Subtask 3 (17%): 2 ≤ *N _{i}* ≤ 1000. ∑

*S*≤ 1000.

_{i}Subtask 4 (17%): 2 ≤ *N _{i}* ≤ 1000. ∑

*S*≤ 100 000.

_{i}Subtask 5 (19%): 2 ≤ *N _{i}* ≤ 10 000. ∑

*S*≤ 200 000.

_{i}Subtask 6 (19%): 2 ≤ *N _{i}* ≤ 200 000. ∑

*S*≤ 200 000.

_{i}Subtask 7 (8%): 2 ≤ *N _{i}* ≤ 10

^{6}. ∑

*S*≤ 10

_{i}^{6}.

Subtask 8 (0%): Sample Testcases

## Sample Testcase 1

### Input

2 1 1 1 3 2

### Output

3 9

### Explanation

There is only one train route, so only this route can be taken.

## Sample Testcase 2

### Input

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

### Output

9 35

### Explanation

An Jun can take the first train route from city 1 to city 2, then switch to the second train route and take it from
city 2 to 3, then switch back to the first train route and take it from city 3 to 5. This gives a total of 3^{2} + 1^{2} + 5^{2} = 35 effective satisfaction.

## Sample Testcase 3

### Input

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

### Output

10 82

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 10 | 8 | 4s | 512MB | Minimum |

2 | 10 | 28 | 4s | 512MB | Minimum |

3 | 17 | 59 | 4s | 512MB | Minimum |

4 | 17 | 65 | 4s | 512MB | Minimum |

5 | 19 | 76 | 4s | 512MB | Minimum |

6 | 19 | 105 | 4s | 512MB | Minimum |

7 | 8 | 139 | 4s | 512MB | Minimum |

8 | 0 | 3 | 4s | 512MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o trains_roi -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512