题目描述

我做了一个重新判断。 休息一段时间后，Joisino 决定与她偶然遇到的一位冒险家一起潜入地牢。 这是一条平坦的道路，但沿途发生了事故，我们不得不赶往安全地带。

这个地牢位于南北各个级别。 R R个人，东西 C C件数，全部 R ∗ C 答∗C房间以网格模式排列。 Joisino的姐妹们在当前楼层最西北的房间里。 安全区将从当前层次结构移动到 N − 1 N−1它是下降层最东南的房间。

除了存在安全区的那个之外，每一层都有几个孔。 洞位于房间内，掉进洞里，可以下降到下一层。 此时，洞口所在的地方是从西北房间向东 x x 向南 和 和 如果是高级房间，你掉进去的房间也是从西北房间到东边。 x x 向南 和 和 这是一个高级房间。 此外，它掉下来的房间里没有洞。 此外，当您进入有洞的房间时，您必须跌倒。

每个房间都有自己的危险级别。 风险越高，穿过房间的风险就越大。 有洞的房间的危险程度是多少？ 0 0但是，应考虑房间坠落后的危险程度。 此外，Joisino 姐姐目前所在的房间和安全区内的房间的危险程度 0 0是。

乔伊西诺的姐妹们想尽可能地避免危险，搬到一个安全区。 为此，我决定选择对我将要走的房间总体风险最小的路线（避免向西或向北行驶的路线）。 Joisino 是一位出色的程序员，他决定创建一个程序来查找通过这种路线旅行的总风险级别。

输入格式

输入来自标准输入，格式如下：

N N R R C C S 1 S 1 ​

S 2 S 2 ​ : S N ∗ R S N∗R ​

1 1要通过行的层次结构数 N ( 2 ≦ N ≦ 100 ) N（2≦N≦100)和一个整数，指示层次结构的大小 R ( 2 ≦ R ≦ 100 ) R（2≦R≦100)和 C ( 2 ≦ C ≦ 100 ) C（2≦C≦100)以空格分隔编写。 2 2从线路 N ∗ R N∗R在行中， K ∗ R + 1 K∗R+1从线路 R R该行包含 K ( 0 ≦ K ≦ N − 1 ) K（0≦K≦N−1)它包含有关下降级别的信息。 这 R R行外 我 我在行中，长度 C C字符串已写入。 此字符串由 和 中的字符组成。 如果第 j 个字母是 ，则它是从西北房间到东边H09H j − 1 j−1 向南 我 − 1 我 -1指示高级房间中有一个孔。 如果第 j 个字母是 ，则它是从西北房间到东边0 j − 1 j−1 向南 我 − 1 我 -1指示您前进到的聊天室是起点或终点。 如果第 j 个字母是介于 和 east 之间的数字，则它是从西北房间到东边19 j − 1 j−1 向南 我 − 1 我 -1表示高级房间的危险级别为该数字。 保证所有输入都至少有一条路线到达安全区。 输出格式 在一行中输出总风险级别的最小值。 此外，在输出末尾包括换行符。

说明/提示 分配 这个问题没有部分意义。 如果您回答正确 60 60获得积分。

示例解释 1

• 向东→向东→ →掉入→洞→向南移动，以最大限度地降低总风险。