About the evil case

It was discovered that an unintended pruning solution passes this problem, so we have decided to add, as an evil case, a case in which the constraint is multiplied by $2$.

We apologize for this.

Problem Statement

There is an undirected graph with $N$ vertices numbered from $1$ to $N$ and $0$ edges. Perform the following operation on this graph $M$ times.

In the $i$-th operation, positive integers $k_i,c_i$ and a sequence $s_1,s_2,\dots,s_{k_i}$ of length $k_i$ are given. For every pair of integers $(x,y)$ satisfying $1\le x < y \le k_i$, add an undirected edge of length $\displaystyle \left\lceil{\frac{s_x+s_y}{2}}\right\rceil + c_i$ connecting vertex $s_x$ and vertex $s_y$. Here, $\displaystyle \lceil x \rceil$ denotes the smallest integer greater than or equal to the real number $x$.

Find the minimum length of a path from vertex $1$ to vertex $N$ in the graph after all $M$ operations have been performed.

If there is no path from vertex $1$ to vertex $N$, output $-1$ instead.

Input

$N\ M$
$k_1\ c_1\ s_{1,1}\ s_{1,2}\ ...\ s_{1,k_1}$
$k_2\ c_2\ s_{2,1}\ s_{2,2}\ ...\ s_{2,k_2}$
$\vdots$
$k_M\ c_M\ s_{M,1}\ s_{M,2}\ ...\ s_{M,k_M}$

The following are the constraints of the evil case. This case does not affect the judgment of correctness. Only the last constraint differs.

Output

Find the minimum length of a path from vertex $1$ to vertex $N$ in the graph after all $M$ operations have been performed.

If there is no path from vertex $1$ to vertex $N$, output $-1$ instead.

Sample

3 1
3 1 1 2 3

3

8 2
4 1000000000 1 2 3 4
4 1000000000 5 6 7 8

-1

18 8
6 11 1 3 5 6 9 13
10 20 2 3 4 6 7 10 13 14 16 17
9 10 1 4 5 10 11 13 14 16 17
10 6 4 5 7 10 11 13 14 15 16 18
2 9 5 12
9 4 2 4 6 8 9 10 14 15 16
7 18 1 2 4 8 10 11 18
4 17 2 3 8 10

28