配点: 20 点
在一条河里,同时从一岸跳到石头上,再跳到对岸,这种有些危险的游戏很流行。
图 4-1 石头的位置示例
现在,像图 4-1 那样,假设石头存在于格子上。行数是 n 。在图 4-1 中是 n = 5 。
在这个游戏中,从一岸开始,通常跳跃或者 m 次以下的一行跳跃,渡到对岸。通常跳跃是指跳到当前行的下一行的岸或石头上,而一行跳跃是指跳到当前行的下一下一行的岸或石头上。开始岸的下一行是 1 行,下一下一行是 2 行,而n − 1 行的下一下一行,以及 n 假设一行的下一行是对岸。
现在,为了尽可能安全地完成这个游戏,我们决定考虑跳跃的危险度。每块石头都有其滑溜程度。从一块石头跳到另一块石头时的跳跃危险度,无论是普通跳跃还是跨一行跳跃,
- (当前石头的滑溜程度 + 跳到的石头的滑溜程度)\times(横向移动距离) 来决定。不过,横向移动距离是指列号的差值。此外,从岸边跳到石头,或者从石头跳到岸边的跳跃危险度为 0 。
输入为 n, m,当给定每块石头的位置和滑溜程度时,编写一个程序求出到达对岸时跳跃危险度的最小值中的最小值。所给的输入数据保证一定能够到达对岸,并且同一个格子中石头不超过 2 块。
入力
输入文件的文件名是 input.txt 。
输入文件的 1 行中,用空格分隔地写着 2 整数 给出 n,m 。这表示行数,以及允许跳过一行的次数。n,m 分别是 代表第 2\leqq n\leqq 150,0\leqq m\leqq \dfrac{(n+1)}2 得到满足。
继续 n 行中,分别写着每行中石头的信息。i+1 行目 (1 \leqq i \leqq n)中有1 整数 k_i (0 \leqq k_i \leqq 10),随后写有 2 \times k_i 个整数,用空格分开。这些表示从起始岸数起,第 i 行中石头的信息。
k_i 表示该行存在的石头数量,接下来的 2 \times k_i 个整数中, 2 \times j - 1 個目 (1 \leqq j \leqq k_i) 的整数 x_{i,j} 表示该行的第 j 块石头的列号,2 \times j 个整数中的第 d_{i,j} 表示该行的第 j 块石头的滑溜度分别表示。x_{i,j},d_{i,j} 分别是 代表第 1 \leqq x_{i,j} , d_{i,j} \leqq 1000 得到满足。
评分数据中,分配的分数 20 对于%, n \leqq 6 和另一个点分配 20 对于%, m = 0 得到满足。
出力
输出文件的文件名是 output.txt 。
output.txt 表示到达对岸时总跳跃风险的最小值
包含 1 整数
由 1 行组成。
例
在图4-2中,石子上写的数字代表每块石子的滑性。
按照箭头指示的顺序穿过石头时,每次跳跃的风险为 0,(2 + 2) \times 1 = 4,(2 + 1) \times 1 = 3,(1 + 4) \times 2 = 10,0 总计为 17 变为。此时,跳跃的总风险是最小的。
该示例对应于输入/输出示例。
图 4-2 路由示例
入力例 1
5 1 2 1 3 2 2 1 3 2 1 1 7 1 2 1 1 4 4
出力例 1
17
上例对应的输入输出如例1。
入力例 2
5 0 2 1 3 2 2 1 3 2 1 1 7 1 2 1 1 4 4
出力例 2
40