Royal Decree

A kingdom has N people. The amount of money each person holds is a non-negative integer, and the people are numbered 1 through N.

One day the king proclaimed a decree. The money any person holds may differ from the money each of that person's friends holds by at most $d$. In other words, for a person to hold $x$, none of that person's friends may hold less than $x-d$ and none may hold more than $x+d$.

Among all distributions that obey the decree, the people want the one where the gap between the richest person and the poorest person is as large as possible.

Given the number of people and the friendships, write a program that computes the largest possible gap.

The first line contains the number of people $N$ ($2 \le N \le 50$).

The second line contains $d$ ($0 \le d \le 1000$).

Each of the next $N$ lines describes the friendships. If the $j$-th character of the $i$-th line is Y, person $i$ and person $j$ are friends; if it is N, they are not. The $i$-th character of the $i$-th line is always N, and the $j$-th character of the $i$-th line equals the $i$-th character of the $j$-th line.

Print on the first line the largest gap between the richest person and the poorest person over all distributions that obey the decree. If this gap is unbounded, print -1.

Suppose there are only three people, person 1 is a friend of person 2, person 2 is a friend of person 3, and $d$ is 10. Giving person 1 100, person 2 110, and person 3 120 obeys the decree, so the gap reaches 20. If nobody is anybody's friend, no constraint applies at all and the gap is unbounded.