柒某人偶然得到一份藏宝图，图中标记一处神秘的雾岛。柒某人觉得雾岛上必定有宝物，于是她带着一帮手下历经千辛万苦终于到达了雾岛外围。当她想进岛取宝藏时，手下探报，前方有一个巨大的矩形迷阵挡在前路。柒某人决定摸清楚迷阵情况，再尝试闯迷阵。
经过勘查，大致了解的迷阵的特点：迷阵由n行m列的房间构成，每个房间与其相邻的上下左右四个房间有门连接，可以通行。在第 i 行的 m 个房间里有 1 个必定触发机关，进入的人就会受到伤害，而且经过勘查，每个房间的机关对人的伤害程度 k 已经查明。假设迷阵的第 1 行和最后一行的房间都是安全的，其中所有在第一行的房间都有门通向迷阵深处。已知一名手下进入迷阵，从第一行的房间到达迷阵最后一行时所受到的伤害是他经过的路径中的房间的伤害值的最大值（即他受到的伤害是他所有受到伤害的最大值）。柒某人的整帮手下受到的伤害值为所有手下的伤害值中的最大值。
柒某人想最大限度保存实力，以便后面寻宝。请帮她计算出最小的伤害代价。
