题目描述

莫船长指挥着他的鹦鹅螺号潜艇，要穿过一个长方形海域。海域被分成 $W$ 的格子，每个格子的水深每分钟变化一次，目呈周期性变化。水深的一个变化周期从 $0$ 开始增加到 $C$，然后再减少到 $0$，具体地说，一个完整的周期为 $0, 1, 2, \ldots, c, c-1, \ldots, 1$。

我们认为同一个格子内的水深是相同的，但是不同格子的水深不一定一样，我们用一个数字和一个字符描述一个格子水深的状态。第 $0$ 分钟时，第行第列的格子的水深为 $0$。之后用一个加号 $+$ 或减号 $-$ 表示下一时刻水深的变化方向，加号表示下一分钟水深会增加，减号表示下一分钟水深会减少。例如，$c = 5$ 时，$2+$ 表示第 $0$ 分钟时水深为 $2$，下一分钟水深会增加。从第 $0$ 分钟起，水深按照 $2, 3, 4, 5, 4, 3, 2, 1, 0, 1$ 为一个周期变化。

第 $0$ 分钟时潜艇在第 $1$ 行第 $1$ 列，每次只能向上下左右的相邻格子移动，移动一个格子需要 $1$ 分钟。潜不能在水深大浅的地方航行，所以船长只能进入水深大于等于$B$的区域。准确地说，如果第 $t$ 分钟时潜艇要移动，只能移动到第 $t+1$ 分钟的水深大于等于 $B$ 的相邻格子。 (也可以原地等待 $1$ 分钟，等水深变化了再移动)

求出从第 $1$ 行第 $1$ 列出发，到达第 $H$ 行第 $W$ 列最少需要的时间。

输入格式

第1行，4个整数 $H, W, C, B$.

接下来 $H$ 行，每行 $W$ 组数据，每组数据由1个整数 $d_{i,j}$ 和 1个字符 $s_{i,j}$ 组成。整数 $d_{i,j}$ 表示第 0 分钟第 $i$ 行第 $j$ 列的水深，字符 $s_{i,j}$ 表示下 1 分钟水深的变化方向，'+' 表示增加，'-' 表示减少。每组数据之间有空格，整数 $d$ 和字符 $s$ 之间没有空格。

输出格式

一个整数，表示从第 1 行第 1 列出发，到达第 $H$ 行第 $W$ 列所需的最少时间。如果无法到达，输出 -1。

样例输入1

3 3 3 2
3- 2+ 2-
1+ 3- 1+
2- 1- 0+

样例输出1

8

样例说明 #1

如下图，每分钟每个格子的深度都写在图上，蓝色潜水艇图标表示鹦鹉螺号的位置，不能进入的格子用红色标出。

样例输入2

3 3 5 4
4- 3- 5-
1+ 0+ 4+
3+ 2- 1-

样例输出2

-1

样例说明 #2

潜艇只能在水深大于等于4的区域航行。第0分钟，潜艇相邻的格子下一分钟的水深都是2，无法移动。第1分钟，潜艇所在的格子水深变成3，小于4，潜艇立刻搁浅，无法到达终点，于是输出-1。

样例输入3

8 5 9 5
9- 5+ 7+ 5+ 0+
6- 2- 7- 0+ 5+
5- 7+ 3+ 1+ 2-
7+ 8- 8+ 8- 4-
1- 9- 6- 9- 3+
3+ 3- 3+ 3- 3+
4- 1+ 7- 0+ 8+
4+ 5- 5- 2+ 5-

样例输出3

28

数据范围

30%数据: $H, W \leq 10$

100%数据: $1 \leq H, W \leq 100$; $1 \leq b \leq c \leq 10$;

$0 \leq d_{i,j} \leq c$; $s_{i,j}$ 是 "+" 或 "-"。