题目描述

照顾新生儿可不是件轻松事，总得有人时刻看着她。同时还有其他家务要做，照顾她的人也想偶尔睡个觉……

有 $n$ 个人一起负责照顾 Bajtolinka。我们考虑时间段 $[0, L)$，它被分成 $L$ 个单位时间片 $[i, i+1)$。对于每个时间片，我们知道谁在忙其他事务。如果某人没被其他事务占用，她可以选择看护 Bajtolinka 或睡觉。

这 $n$ 个人在整个时间段内，每人最多只会睡一次觉并醒来一次。为了公平起见，我们希望安排一个计划，让每个人都能睡同样长的时间 $T$（$T$ 是一个非负实数）。其他事务会占满整个时间片 $[i, i+1)$，而睡眠可以占用任意区间 $[a, a+T)$，其中 $a$ 是非负实数且满足 $a+T \leq L$。

请你找出最大的 $T$，使得所有 $n$ 个人都能安排睡眠，同时保证任意时刻 $x \in [0, L)$ 至少有一个人能照顾 Bajtolinka（即她没在睡觉也没被其他事务占用）。可以证明，最优的 $T$（如果存在）是一个有理数，请以不可约分数形式输出。如果无法安排计划让整个时间段都有人看护，输出 $-1$。

输入格式

输入的第一行包含两个整数 $n, L$ $(1 \leq n \leq 18, 1 \leq L \leq 100000)$，分别表示照顾 Bajtolinka 的人数和时间段的总长度。

接下来的 $n$ 行，每行是一个长度为 $L$ 的字符串，由字符 X 和 . 组成，描述每个人在各时间片的其他事务。第 $i$ 个字符对应时间片 $[i-1, i)$：

• X 表示此人忙于其他事务；
• . 表示此人空闲，可以睡觉或照顾 Bajtolinka。

输出格式

如果无法安排计划，输出一行，包含数字 $-1$。否则，输出一行，包含一个不可约分数 $x / y$（满足 $\gcd(x, y)=1$ 且 $y > 0$），表示在最优安排下每个人能睡的最大时间。

3 6
..X.XX
.X..X.
X..X..

4/3

在第一个样例中，为了得到结果 $\frac{4}{3}$，这些人必须分别在时间段 $\left[0, \frac{4}{3}\right),\left[\frac{8}{3}, 4\right),\left(\frac{4}{3}, \frac{8}{3}\right)$ 睡觉。

3 2
..
XX
..

0/1

在第二个样例中，第二个人一直忙于其他事务，所以没时间睡觉。

1 3
.X.

-1

在第三个样例中，在时刻 $x=\frac{\pi}{2} \approx 1.57$，没有人能照顾 Bajtolinka。