evilケースについて

本問題で、想定していなかった枝刈り解法が通ってしまうことが発覚したため evil ケースとして制約を $2$ 倍にしたケースを evil ケースとして追加することにします。

申し訳ありません。

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点 $0$ 辺の無向グラフがあります。このグラフに対し、以下の操作を $M$ 回行います。

$i$ 回目の操作では正整数 $k_i,c_i$ と長さ $k_i$ の数列 $s_1,s_2,\dots,s_{k_i}$ が与えられます。 $1\le x < y \le k_i$ を満たす全ての整数の組$(x,y)$ に対し、 頂点 $s_x$ と頂点 $s_y$ を結ぶ長さ $\displaystyle \left\lceil{\frac{s_x+s_y}{2}}\right\rceil + c_i$ の無向辺を貼ります。 ただし、 $\displaystyle \lceil x \rceil$ は 実数 $x$ 以上の最小の整数のことを表します。

$M$ 回の操作が終了した時点でのグラフにおいて、頂点 $1$ から頂点 $N$ へのパスの長さの最小値を求めてください。

ただし、頂点 $1$ から頂点 $N$ へのパスが存在しない場合は代わりに $-1$ を出力してください。

入力

$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}$

以下は evil ケースの制約です。このケースは正誤判定に影響しません。一番下の制約のみが変わっています。

出力

$M$ 回の操作が終了した時点でのグラフにおいて、頂点 $1$ から頂点 $N$ へのパスの長さの最小値を求めてください。

ただし、頂点 $1$ から頂点 $N$ へのパスが存在しない場合は代わりに $-1$ を出力してください。

サンプル

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