칙령

N명이 사는 왕국이 있다. 각 사람이 가진 돈은 음이 아닌 정수이고, 사람에게는 1번부터 N번까지 번호가 붙어 있다.

어느 날 왕이 칙령을 선포했다. 모든 사람이 가진 돈은 자기 친구가 가진 돈과 최대 $d$원까지만 차이가 날 수 있다. 즉 어떤 사람이 $x$원을 가지려면, 그 사람의 친구 중에 $x-d$원보다 적게 가진 사람도, $x+d$원보다 많이 가진 사람도 없어야 한다.

사람들은 칙령을 지키는 분배 중에서 돈을 가장 많이 가진 사람과 가장 적게 가진 사람의 차이가 가장 크게 되도록 돈을 나누려고 한다.

사람의 수와 친구 관계가 주어졌을 때, 그 차이의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 사람의 수 $N$ ($2 \le N \le 50$)이 주어진다.

둘째 줄에 $d$ ($0 \le d \le 1000$)가 주어진다.

셋째 줄부터 $N$개의 줄에 사람들의 친구 관계가 주어진다. $i$번째 줄의 $j$번째 문자가 Y이면 $i$번 사람과 $j$번 사람이 친구라는 뜻이고, N이면 친구가 아니라는 뜻이다. $i$번째 줄의 $i$번째 문자는 항상 N이며, $i$번째 줄의 $j$번째 문자와 $j$번째 줄의 $i$번째 문자는 같다.

칙령을 지키는 분배 중에서 돈을 가장 많이 가진 사람과 가장 적게 가진 사람의 차이가 최대일 때, 그 차이를 첫째 줄에 출력한다. 이 차이가 무한대인 경우에는 -1을 출력한다.

1번과 2번이 친구이고 2번과 3번이 친구인 세 사람만 있고 $d$가 10이라면, 1번이 100원, 2번이 110원, 3번이 120원을 갖는 분배가 칙령을 지키므로 차이는 20까지 커진다. 반대로 친구 관계가 하나도 없으면 아무런 제약이 없으므로 차이는 무한대다.