Royal Decree

Interview

Time limit2sMemory limit512 MB

Summary

Given a friendship graph and bound d, find the largest possible difference between richest and poorest that satisfies the friend-difference constraint, or -1 if unbounded.

Level: Medium6 of 10
Topics: Graph, Shortest path, BFS
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Explanation

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.

Examples3

Example 1
Input
```
3
10
NYN
YNY
NYN
```
Expected output
```
20
```
Example 2
Input
```
2
1
NN
NN
```
Expected output
```
-1
```

Example 3

Input

6
1000
NNYNNN
NNYNNN
YYNYNN
NNYNYY
NNNYNN
NNNYNN

Expected output