题目内容

勇者小明被困在一座 $m$ 行 $n$ 列的地牢中，地牢的每个房间 $(i,j)$ 都标注了 “进入成本”（单位：金币）—— 进入该房间需消耗对应数量的金币。小明的初始位置是地牢左上角的房间 $(0,0)$，目标是到达右下角的宝藏房间 $(m - 1,n - 1)$，并尽可能减少金币消耗。

小明拥有两种移动方式：

• 常规行走：从当前房间 $(i,j)$ 只能向右走到 $(i,j + 1)$ 或向下走到 $(i + 1,j)$，进入目标房间后，需支付该房间标注的金币（即消耗等于目标房间的 “进入成本”）；
• 传送卷轴：小明最多可使用 $k$ 次传送卷轴。使用时，可从当前所在房间 $(i,j)$ 直接传送到任意满足 “目标房间进入成本 $≤$ 当前所在房间进入成本” 的房间 $(x,y)$，传送过程不消耗任何金币（成本为 $0$）。