[SCOI2006] 城堡

题目描述

为了救出心爱的公主 Julie,Billy 来到了恶魔的城堡。经过了三天三夜的浴血奋战,魔王殿已近在咫尺。 这是一条狭长的通道,Billy 在位置 $0$,而魔王殿在位置 $n + 1$。在每个单位时间,Billy 可以往左或往右移动一个单位,或者原地不动。每个格子的上方都有石头周期性的往下砸,格子 $i$ 的周期为 $c_i$。 对于格子 $i$ 上方的石头,可以用 $c_i$ 个整数来描述:$h_1, h_2, \cdots, h_{c_i}$,表示在时间 $t = kc_i + x$($1\leq x\leq c_i$)时处于该格子上将被砸掉 $h_x$ 格血。其中 $h_x = 0$ 表示该时刻没有石头砸下来。 计算 Billy 最少损失多少格血后可以到达魔王殿。假设 Billy 是不会死的。注意从位置 $1$ 也是可以回到位置 $0$ 的,且在位置 $0$ 不损血。

输入输出格式

输入格式


第一行包括一个整数 $n$,表示通道的长度。 以下 $n$ 行,依次表示格子 $1, 2, \cdots, n$ 的情况。每行第一个整数为 $c_i$,表示石头下落周期,接下来有 $c_i$ 个整数,分别为 $h_1, h_2, \cdots, h_{c_i}$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

对于 $50\%$ 的数据,$n\leq 20$; 对于 $100\%$ 的数据满足:$0\leq n\leq 1000$,$1\leq c_i\leq 10$,$0\leq h_x\leq 100$。 - 2023.4.12 添加一组 hack 数据,不计分。