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 ith train route visits Si + 1 cities numbered Vi1, Vi2, ... , ViSi + 1. Travelling between city Vi1 and city Vi2 takes Ti1 time, travelling between city Vi2 and city Vi3 takes Ti2 time, ... , travelling between city ViSi and city ViSi + 1 takes TiSi time for the ith 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 ith line begins with an integer Si, followed by 2 × Si + 1 integers, Vi1, Ti1, Vi2, Ti2, ... , ViSi, TiSi, ViSi + 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 ≤ 106. 1 ≤ Tij ≤ 1000. 1 ≤ Si ≤ 106. ∑ Si ≤ 106.

Subtask 1 (10%): 2 ≤ Ni ≤ 10. ∑ Si ≤ 20. Si = 1.

Subtask 2 (10%): 2 ≤ Ni ≤ 1000. ∑ Si ≤ 1000. Si = 1.

Subtask 3 (17%): 2 ≤ Ni ≤ 1000. ∑ Si ≤ 1000.

Subtask 4 (17%): 2 ≤ Ni ≤ 1000. ∑ Si ≤ 100 000.

Subtask 5 (19%): 2 ≤ Ni ≤ 10 000. ∑ Si ≤ 200 000.

Subtask 6 (19%): 2 ≤ Ni ≤ 200 000. ∑ Si ≤ 200 000.

Subtask 7 (8%): 2 ≤ Ni ≤ 106. ∑ Si ≤ 106.

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 32 + 12 + 52 = 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