题目描述

Carl 决定去抱石馆锻炼。他尝试攀爬一面较简单的墙，但总会因为体力耗尽而无法到达顶端。

攀岩墙上的岩点具有不同形状，抓住不同岩点会消耗不同数量的体力。请帮助 Carl 找出一条在体力耗尽之前到达顶端的最短路线。

攀岩墙是一个由 $1\times1$ 单元格构成的矩形网格。忽略岩点本身的大小，可认为每个岩点都是位于对应单元格正中心的一个点。

只有当两个岩点中心之间的欧几里得距离不超过 Carl 的臂展 $r$ 时，他才能从其中一个岩点移动到另一个岩点。

上图展示了样例 1 的岩点和一条可行路线。

输入格式

第一行包含四个整数 $h,w,r,s$：

• $h$（$2\le h\le25$）表示攀岩墙高度；
• $w$（$1\le w\le25$）表示攀岩墙宽度；
• $r$（$1\le r\le3$）表示 Carl 的臂展；
• $s$（$1\le s\le10^9$）表示 Carl 的体力上限。

接下来 $h$ 行，每行包含 $w$ 个字符，用来描述墙上的岩点。每个字符为：

• 数字字符 1 到 9：该位置存在一个岩点，其难度为对应数字；
• .：该位置没有岩点。

第一行对应攀岩墙最上方的一行，最后一行对应最下方的一行。

一条岩点序列是合法路线，当且仅当满足：

1. 路线从纵坐标最低的岩点开始，在纵坐标最高的岩点结束；题目保证最低岩点和最高岩点都唯一，且二者不同；
2. 路线上使用的所有岩点难度之和不超过 $s$；
3. 路线上任意两个相邻岩点中心之间的欧几里得距离不超过 $r$。

输出格式

若 Carl 能够到达最高岩点，输出满足体力限制的最短路线总长度。

若无法到达，输出：

impossible

对于数值答案，绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

样例 1

输入

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

输出

13.543203766865055

样例 2

输入

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

输出

6.414213562373095

样例 3

输入

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

输出

impossible