在经历了几个漫长的下午，整晚沉迷于电子游戏之后，Carl 终于决定开始执行他的新年计划——去抱石馆攀岩。

在那里，他尝试攀爬一面较简单的墙，但遗憾的是，他总是无法到达顶部，因为他总是体力耗尽而掉下来。

在攀爬过程中，他注意到所有的岩点形状各异，有些岩点比其他的更难抓握，因此抓握它们会消耗不同数量的体力。沮丧之余，他向馆内的一位常客——也就是你——请教如何攀登这面墙。请为他找出一条最短的攀登路线，要求他在体力耗尽之前能够到达顶部。

抱石墙是一个 $1 \times 1$ 大小的网格，岩点可以安装在网格中。对于本题，我们不考虑岩点的大小差异，你可以假设它们是位于网格中心的一个点。Carl 只有在两个岩点之间的距离（网格中心之间的欧几里得距离）不超过他手臂的伸展范围时，才能从一个岩点移动到另一个岩点。

图 B.1：样例 1

输入格式

输入包含： 一行包含四个整数 $h, w, r$ 和 $s$ ($2 \le h \le 25, 1 \le w \le 25, 1 \le r \le 3, 1 \le s \le 10^9$)，其中 $h$ 和 $w$ 是抱石墙的高度和宽度，$r$ 是 Carl 手臂的伸展范围，$s$ 是 Carl 体力的数值表示。 $h$ 行，每行包含 $w$ 个字符，描述抱石墙上的岩点。每个字符要么是一个数字 $c$ ($1 \le c \le 9$)，表示该位置安装了一个难度为 $c$ 的岩点；要么是 “.”，表示该位置没有安装岩点。

第一行对应抱石墙的顶部，最后一行对应底部。

如果满足以下条件，则岩点序列是 Carl 的一条有效路线： 路线从最底部的岩点开始，到最顶部的岩点结束。保证存在唯一的最低岩点和唯一的最高岩点，且它们互不相同。 所使用岩点的难度总和不超过 $s$。 * 路线上任意两个连续岩点之间的欧几里得距离不超过 $r$。

输出格式

输出 Carl 在体力不耗尽的情况下到达最高岩点的最短路线总长度。你的答案应具有不超过 $10^{-6}$ 的绝对或相对误差。如果 Carl 无法到达顶部，则输出 impossible。

样例

样例输入 1

12 11 3 11
...........
........3..
.......3.1.
...........
.......2...
.....2.....
.1.1.......
.....2.....
.1.........
...2.......
.1.........
...........

样例输出 1

13.543203766865055

样例输入 2

8 16 3 15
......1.........
....1..1.1......
..2........1....
...2......1.....
.....4.1..2..1..
................
.......1........
................

样例输出 2

6.414213562373095

样例输入 3

10 10 2 10
...2......
..........
...5.2....
..........
.....3....
....5.....
..2....2..
..1.......
....2.....
..1.......

样例输出 3

impossible