旅行者在国家间的旅行从来都不是一件简单的事，尤其是当城市之间没有直达交通时。一群游客想要利用连接 $n$ 个城市的铁路网前往“大都市”（Metropolis）。游客出发的城市编号为 $1$，大都市的编号为 $n$。

铁路网上持续运行着 $m$ 条火车线路。每条线路都由一系列城市定义，按火车经过的顺序排列。对于每条线路，每一对相邻城市之间都给出了火车行驶这段路程所需的时间。不同线路的火车通过同一路段所需的时间可能不同。

在前往大都市的途中，游客可以在线路上的任何城市上车或下车，而不必在起点或终点站。此外，游客可以从线路 $i$ 的火车下车，换乘线路 $j$ 的火车，可能还会进行多次换乘，之后还可以再次乘坐线路 $i$ 的火车。

游客对前往大都市的交通方式有很高的要求： 首先，在火车上花费的总时间必须最短。 其次，在所有总时间最短的交通方式中，优先选择那种“连续在火车上行驶的各段路程时间平方和”最大的方式。我们将这个总和称为“旅行质量”。

在火车外花费的时间不计入总时间。

你需要编写一个程序，根据现有的火车线路描述，确定游客在火车上必须花费的最短总时间，以及在该时间下的最大旅行质量。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^6, 1 \le m \le 10^6$)，分别表示城市数量和线路数量。

接下来 $m$ 行包含线路描述。 每条线路的描述以整数 $s_i$ 开头，表示线路 $i$ 中的路段数量 ($1 \le s_i \le 10^6$)。随后是 $2s_i + 1$ 个整数，按以下顺序描述线路的城市和相邻城市间的行驶时间：$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}$，其中 $v_{i,j}$ 是线路中第 $j$ 个城市的编号，$t_{i,j}$ 是第 $j$ 个城市与第 $(j+1)$ 个城市之间路段的行驶时间 ($1 \le v_{i,j} \le n, 1 \le t_{i,j} \le 1000$)。

保证 $\sum s_i \le 10^6$。线路描述中不会出现两个相同的城市（即线路内无环）。保证可以通过现有线路从城市 $1$ 到达城市 $n$。

输出格式

输出两个整数：在火车上花费的最短总时间，以及在该时间下的最大旅行质量。

样例

样例 1

2 1
1 1 3 2

3 9

样例 2

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

9 35

样例 3

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

10 82

说明

在第一个样例中，游客直接乘坐线路前往大都市。

在第二个样例中，直接乘坐第一条线路并不是最优的，因为此时在火车上的总时间不是最小的。因此，他们先乘坐线路 $1$ 从城市 $1$ 到城市 $2$，然后乘坐线路 $2$ 从城市 $2$ 到城市 $3$，最后再次乘坐线路 $1$ 从城市 $3$ 到城市 $5$。此时，各段连续乘车时间平方和为 $3^2 + 1^2 + 5^2 = 35$。

第二个样例的示意图。

在第三个样例中，从城市 $1$ 到城市 $4$ 的最短时间路径可以通过在城市 $2, 3$ 或 $4$ 换乘线路 $1$ 和线路 $2$ 来实现。在城市 $2$ 换乘时可达到最大旅行质量：$1^2 + 9^2 = 82$。