[SCOI2006]城堡

题目描述

为了救出心爱的公主Julie，Billy来到了恶魔的城堡。经过了三天三夜的浴血奋战，魔王殿已近在咫尺。

这是一条狭长的通道，Billy在位置0，而魔王殿在位置n+1。在每个单位时间，Billy可以往左或往右移动一个单位，或者原地不动。每个格子的上方都有石头周期性的往下砸，格子i的周期为ci。对于格子i上方的石头，可以用ci个整数来描述：h[1], h[2], …, h[ci]，表示在时间t=kci+x（1<=x<=ci）时处于该格子上将被砸掉h[x]格血。其中h[x]=0表示该时刻没有石头砸下来。

计算Billy最少损失多少格血后可以到达魔王殿。假设Billy是不会死的。注意从位置1也是可以回到位置0的，且在位置0不损血。

输入格式

第一行包括一个整数n，表示通道的长度。

以下n行，依次表示格子1, 2, 3, …, n的情况。每行第一个整数为ci(1<=ci<=10)，表示石头下落周期，接下来有ci个整数，分别为h[1], h[2], ..., h[ci]。(0<=h[x]<=100)

输出格式

包含一个整数HP，表示血的最小损失。

样例 #1

样例输入 #1

4
2 1 0
2 0 1
1 2
7 0 1 1 1 1 1 1

样例输出 #1

2

提示

50%的数据满足：0<=n<=20

100%的数据满足：0<=n<=1000