Traveling across the country is never simple, especially when there is no direct connection between cities. A group of tourists wants to reach the city of Metropolis using a railway network that connects $n$ cities, numbered from 1 to $n$. The city from which the group departs is numbered 1, and Metropolis is numbered $n$.

There are $m$ train routes constantly operating on the railway. Each route is defined by a sequence of cities listed in the order the train serving that route visits them. For each route, the time taken for the train to travel the segment between each pair of consecutive cities is specified. Note that trains on different routes may traverse the same segment in different amounts of time.

On the way to Metropolis, the group can board and exit a train at any city on the route, not necessarily at the start or end. It is possible to exit a train on route $i$, transfer to a train on route $j$, potentially make several more transfers, and then board a train on route $i$ again.

The tourists have high requirements for choosing their travel method to Metropolis. First, the total time spent on trains must be minimal. Second, among all methods with the minimal total time spent on trains, the preferred method is the one for which the sum of the squares of the time intervals spent continuously on a train between two transfers is maximal. We call this sum the quality of the trip.

Time spent outside of trains is not taken into account.

You are required to write a program that, given the descriptions of the available train routes, determines the minimum time the group of tourists will have to spend on trains, as well as the maximum quality of the trip with that time.

Input

The first line of the input contains two integers ($2 \le n \le 10^6$, $1 \le m \le 10^6$) — the number of cities and the number of routes, respectively.

The following $m$ lines contain the descriptions of the routes.

The description of each route starts with an integer $s_i$ — the number of segments in route $i$ ($1 \le s_i \le 10^6$). This is followed by $2s_i + 1$ integers describing the cities of the route and the travel time for each segment between consecutive cities, in the following order: $v_{i,1}, t_{i,1}, v_{i,2}, t_{i,2}, v_{i,3}, \dots, t_{i,s_i}, v_{i,s_i+1}$, where $v_{i,j}$ is the number of the $j$-th city on the route, and $t_{i,j}$ is the travel time of the segment between the $j$-th and $(j+1)$-th city ($1 \le v_{i,j} \le n$, $1 \le t_{i,j} \le 1000$).

It is guaranteed that $s_1 + s_2 + \dots + s_m \le 10^6$. No two cities in a route description are the same. It is guaranteed that it is possible to reach the city numbered $n$ from the city numbered 1 using the available routes.

Output

The output must contain two integers — the minimum total time that must be spent on trains, and the maximum quality of the trip with that time.

Examples

Input 1

2 1
1 1 3 2

Output 1

3 9

Input 2

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

Output 2

9 35

Input 3

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

Output 3

10 82

Note

In the first example, the group of tourists takes a direct route to Metropolis.

In the second example, it is not optimal to travel directly along the first route, as the time spent on the train would not be the minimum possible. Therefore, they take the train on route 1 from city 1 to city 2, then the train on route 2 from city 2 to city 3, and then again the train on route 1 from city 3 to city 5. In this case, the sum of the squares of the time intervals spent on trains between transfers is $3^2 + 1^2 + 5^2 = 35$.

Illustration for the second example.

In the third example, the way to reach city 4 from city 1 in the minimum time is to transfer from route 1 to route 2 at any of the cities 2, 3, or 4. The maximum quality of the trip is achieved by transferring at city 2: $1^2 + 9^2 = 82$.

Please note that the second and third examples do not satisfy the constraints of the first and second subtasks; the solution will be tested on these subtasks if it passes the first test from the example. All tests from the example fit the constraints of subtasks 3–7; the solution will be checked on the tests of these subtasks only if it passes all tests from the example.

Subtasks