\texttt{WalkerV} 进入高中后,他发现作业量越来越大。这不仅使得初来乍到的同学们措手不及,更是让收作业的课代表们叫苦不迭。
现在,\texttt{WalkerV} 班上的课代表找到了他,希望他能够帮忙设计一条最优路线,使得他们在收作业时能走尽量少的路。\texttt{WalkerV} 希望你能帮忙解决这个问题。
\texttt{WalkerV} 班教室中的桌子共有 n 列,每一列为一个小组,共有 m 张桌子。因此,我们可以将其视作一个 n \times m 的平面。
课代表需要收若干位同学的作业。对于第 i 列,共有 $s{i} 位同学需要交作业,分别是这一列的第 a{i1}, a{i2}, \cdots ,a{is{i}} 行的同学(即坐标 (i,a{i1}),(i,a{i2}), \cdots (i,a{is_{i}})$)。
现在,课代表将从 (1,1) 处出发开始收作业,在到达 (x,y) 处时收取该处的作业,并最终到达 (n,m) 处。为了使作业是按小组分好的,他必须一列一列的收(即收完第 i 列的所有作业后才能前往第 i+1 列)。
更具体地说,课代表在任何时候都只能做如下三种移动之一:
此三种移动的路程都是 1。
现在,请你求出最短的路程长度。
共 n+1 行。
第一行,两个整数 n,m。
接下来 n 行,第 i 行(总第 i+1 行)有 s_i+1 个整数。第一个数为 s_i,后有 $si 个数,分别为 a{i1},a{i2}, \cdots ,a{is_i}$。
一行一个整数 ans,表示最短的路程长度。
2 3 2 2 3 1 1
7
6 6 3 2 3 6 2 3 4 3 2 1 3 2 2 1 4 5 4 3 6 2 4 5
24
6 6 2 2 3 4 4 3 5 2 3 2 4 6 2 4 1 3 5 6 3 2 1 4
32
对于 10\% 的数据,n \leq 3,m \leq 3。
对于 100\% 的数据,1 \leq n \leq 2 \times 10^4,1 \leq m \leq 2 \times 10^4,1 \leq s_i \leq 20。