9117 - [SF Round 3] 收作业(homework)

\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)。

更具体地说,课代表在任何时候都只能做如下三种移动之一:

  • 向前移动一行(即从 (x,y) 处移动到 (x,y+1) 处)
  • 向后移动一行(即从 (x,y) 处移动到 (x,y-1) 处)
  • 向右移动一列(即从 (x,y) 处移动到 (x+1,y) 处)

此三种移动的路程都是 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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题