题目描述

You have an egg carton that can be represented as a $3 \times N$ grid. The grid consists of 3 rows, numbered from 1 to 3, and $N$ columns, numbered from 1 to $N$. The cell at row $r$ and column $c$ is denoted as $(r, c)$. Each cell can be either usable or unusable; each usable cell can only hold at most 1 egg while unusable cells, as the name implies, cannot be used.

You want to put exactly $K$ eggs into usable cells of your carton such that the distance between any two closest eggs is maximized. The distance between an egg in cell $(r_1, c_1)$ and another egg in cell $(r_2, c_2)$ can be calculated using Euclidean distance, i.e. $\sqrt{(r_1 - r_2)^2 + (c_1 - c_2)^2}$.

Determine the maximum possible distance between any two closest eggs, or determine if it is impossible to put $K$ eggs into your carton.

输入格式

Input begins with two integers $N$ $K$ ($1 \leq N \leq 100$; $2 \leq K \leq 3N$) representing the number of columns of your egg carton and the number of eggs. Each of the next 3 lines contains a string $S_r$ of length $N$ that consists of either character '.' or '#'. The $c^{th}$ character of string $S_r$ represents the condition of cell $(r, c)$ of the carton. Cell $(r, c)$ is usable if $S_{r,c} = \tt{.}$ and unusable if $S_{r,c} = \tt{\#}$.

输出格式

If $K$ eggs can be put into your carton, then output a real number in a single line representing the maximum possible distance between any two closest eggs. Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

If $K$ eggs cannot be put into your carton, then output $-1$ in a single line.

5 2
#....
.....
....#

4.472136

提示

Explanation for the sample input/output #1

The maximum distance between any two closest eggs can only be achieved by putting the eggs in cells $(3,1)$ and $(1,5)$, where the distance between the two (closest) eggs is $\sqrt{20}$.