题目描述

你生活在一个有 $n$ 座车站和 $m$ 条铁路线路的城市。第 $i$ 条铁路有 $L_i$ 座车站，分别经过 $s_{i,0},s_{i,1},\dots,s_{i,L-1}$ 车站。车站 $s_{i,j}$ 到 $s_{i,j+1}$ 之间的距离为 $w_{i,j}$。你希望从 $src$ 车站出发前往 $dst$ 车站。

你熬了夜，所以你很困，可能在某一个从 $x$ 车站到 $y$ 车站的区间中睡着。如果你睡着了，你将沿着列车的行进方向一直到达这一方向上的终点站。然后，你会觉得神清气爽，因此你将可以任意乘坐或换乘列车而不会再睡着。

在你熬夜前，你已经预料到了这种情况，但你无法确定你在什么时候睡着。因此，你希望求出，在最优策略下，最小的能保证无论你在什么时候睡着都能在 $T$ 时间内到达 $dst$ 的 $T$ 的值是多少。

输入格式

输入第一行为 $n,m$，空格分隔。

以下 $3m$ 行：

• 第 $3i-1$ 行为一个整数 $L_i$。
• 第 $3i$ 行为 $L_i$ 个整数 $s_{i,0},s_{i,1},\dots,s_{i,L-1}$。
• 第 $3i+1$ 行为 $L_i-1$ 个整数 $w_{i,0},w_{i,1},\dots,w_{i,L-2}$。

输出格式

输出一行一个整数，表示最小的 $T$。

样例 #1

样例输入 #1

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

样例输出 #1

6

样例 #2

样例输入 #2

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

样例输出 #2

8

样例 #3

样例输入 #3

4 2 0 1
3
0 1 2
1 3
3
0 3 1
1 1

样例输出 #3

2

提示

【样例 1 解释】

一种最优的方案是：

• 从 $0$ 出发向 $2$ 方向乘车，预计在 $1$ 下车。
• 如果在 $0 \rightarrow 1$ 睡着，那么到达 $2$ 并从 $2$ 返回 $1$，总时长 $6$。
• 如果在 $1 \rightarrow 3$ 睡着，那么到达 $4$ 并从 $4$ 返回 $3$，总时长 $4$。

则 $T=6$。可以证明，没有更优的方案。

【数据规模与约定】

对于所有数据，$2 \le n \le 25252, L_i \ge 2, \sum L_i \le 252525, 1 \le w_{i,j} \le 2525, 1 \le s_{i,j} \le n$，且不存在 $x \ne y$ 且 $s_{i,x} = s_{i,y}$。