小A在历经一系列冒险之后终于得知了宝藏的方位。在经过调查之后，小A在地图上标注了自己的位置和宝藏的位置，当然，沿途充满着危险，一些位置无法经过，并且其余位置每走一步都需要消耗掉一定量的体力和花费一定量的时间。

在体力为 0 时无法移动，万幸的是，一些位置有神奇的草药并且可以无限采摘，吃下就会立即回复一定量的体力。

小A想知道自己最快多久可以到达宝藏的所在地。

给定一个大小为 n\times m 的矩阵地图，一个起点坐标为 (sx,sy)，一个终点坐标为 (ex,ey)。从起点出发，每次可以选择往上下左右四个方向移动一格，每次移动花费 1 单位时间以及 1 单位体力。小A的初始体力大小和体力上限为 k，当体力减小为 0 之后无法再移动。

地图上的每个格子用一个字符表示，格子有下面三种情况：

      . ：表示这个格子可以移动。

      # ：表示这个格子为障碍物，无法移动。

      一个个位数字 x，（$1\le x\le9$）：表示移动到这个格子之后，会恢复 x 点体力，如果移动到该格子体力为0，那么也会恢复 x 点体力。注意恢复体力无法超过体力的上限。每次经过都可以恢复体力，到达终点时的体力可以为 0。

保证起点和终点的位置一定为 . 。

从文件treasure.in中读入数据。

输入的第一行包括 7 个整数 n,m,sx,sy,ex,ey,k，分别表示地图行数和列数、起点、终点、初始体力及最大体力。

接下来 n 行，每行 m 个字符，表示矩阵地图每个格子的信息。

输出到文件treasure.out中。

输出仅1个数字，如果能够到达，则输出最快到达的时间；如果永远不可能到达，输出 -1 。

在样例中，起点为 (2,2)，终点为 (2,8)，唯一的方案为从起点一直走到 (1,6)，吃完草药再直接前往终点，一共需要 8 步。

对于所有测试数据保证：$1\le n,m\le1000，1≤k≤10$。