以下题面由 AI 翻译。

问题描述

伯纳德经常迟到，总是无法及时过河。他的问题是必须乘船过河。鲁道夫决定帮助他的朋友解决这个问题。

河流是一个由 $n$ 行和 $m$ 列组成的网格。第 $i$ 行和第 $j$ 列的交点包含数字 $a_{i,j}$——对应单元格的深度。所有第一列和最后一列的单元格对应河岸，因此它们的深度为 $0$。

下图显示了河流的可能形状：

鲁道夫可以选择第 $(i,1), (i,2), \ldots, (i,m)$ 行建桥。在该行中的每个单元格都可以安装支撑。安装支撑的成本是 $a_{i,j}+1$。必须满足以下条件：

1. 在单元格 $(i,1)$ 安装支撑；
2. 在单元格 $(i,m)$ 安装支撑；
3. 相邻支撑之间的距离不能超过 $d$。两个支撑 $(i, j_1)$ 和 $(i, j_2)$ 之间的距离是 $|j_1 - j_2| - 1$。

建一座桥很无聊，因此鲁道夫决定在连续的行上建 $k$ 座桥，即选择某个 $i$（$1 \leq i \leq n$），并在第 $i, i+1, \ldots, i+k-1$ 行建桥。