题目描述

游戏是在一个无环的无向图中进行的，每个点上面有一些金币。

每次小K可以对一个金币大于等于 $2$ 的点，拿走一个金币，并将另一个金币放到它相邻的点上。而游戏中有一个点叫做 Target Point，如果在游戏的过程中 Target Point上有金币的话，小K就赢了。

巧合的是这个游戏是小Z开发的，在得知小K在玩这个游戏之后，为了报上次的一箭之仇，他决定设计金币的分布让小K必败。而小Z深知小K的光环的威力，如果放置的金币太少，小K会马上发现这个游戏是不可能赢的。于是他求助于你，他最多能放多少个金币呢？

输入格式

本题有多组数据。

第一行，两个整数 $N,M(1 \leq M \leq N \leq 60)$，表示共有 $N$ 个节点，而 $M$ 为 Target Point。

接下来有 $N$ 行，每行为一个长度为 $N$ 的字符串。如果第 $i$ 个字符串的第 $j$ 个字符是 Y，则代表 $i$ 与 $j$ 之间有边。

输出格式

输出最多能放多少个金币。如果答案超过了 $2 \times 10^9$，则输出 $-1$。

输入样例

3 2
NYN
YNY
NYN
1 1
N

输出样例

2
0