32176번 - 통신 시스템의 성능 저하

문제

주영이는 통신 시스템의 정비사이다. 주영이는 마을의 정보가 주어졌을 때, 마을에서 발생하는 통신 성능을 모델링하고 싶다.

마을은 $N \times N$ 크기의 격자로 표현할 수 있다. $(r, c)$는 $r$행 $c$열의 칸을 의미하며 각 칸은 기지국, 노드, 빈칸 중 하나이다. 기지국은 노드의 모든 통신을 관리하는 곳으로 마을에서 1ドル$개만 존재한다. 노드는 데이터 교환이 일어나는 곳으로 마을에서 $M$개만 존재하며 처음에는 모두 비활성화되어 있다.

주영이는 일부 노드를 활성화해 통신 성능을 모델링한다. 모델링에 있어 통신에 큰 왜곡이 발생할 수 있다. 따라서 왜곡으로 인한 최대 통신 성능의 저하 수치를 고려해야 한다.

• $P$ (경로 손실) : 기지국과 활성화된 각 노드 사이의 거리의 총합. 서로 다른 두 칸 $(a, b),ドル $(c, d)$ 사이의 거리는 $|a - c| + |b - d|$로 계산한다.
• $U$ (사용자 산포도) : 활성화된 모든 노드를 포함하는 최소 직사각형의 넓이. 이때 직사각형의 변은 $x$축 혹은 $y$축에 평행해야 한다.
• $C$ (통신 성능 저하 수치) : $\max(P - U, 0)$
• 최대 통신 성능의 저하 수치 : 가능한 $C$ 값 중 최댓값이다. 만약 아무 노드도 활성화하지 않을 경우 0ドル$이다.

노드는 낮에는 $K_1$개, 밤에는 $K_2$개 활성화해야 한다. 주영이를 위해 낮과 밤에 해당하는 최대 통신 성능 저하 수치를 각각 구해주자.

입력

첫 번째 줄에 $N,ドル $M,ドル $K_1,ドル $K_2$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 마을의 정보가 주어진다. 그중 $i$번째 줄에는 길이가 $N$인 문자열이 주어진다. 그중 $j$번째 문자 $c_{ij}$는 $(i, j)$칸의 정보를 의미한다. 칸의 정보가 F라면 빈칸, B라면 기지국, N이라면 비활성화된 노드를 의미한다.

출력

첫 번째 줄에 낮의 최대 통신 성능의 저하 수치를 출력한다.

두 번째 줄에 밤의 최대 통신 성능의 저하 수치를 출력한다.

제한

• 2ドル \le N \le 6$
• 0ドル \le M \le N^2 - 1$
• $\max(M - 4, 0) \le K_1 \le M$
• 0ドル \le K_2 \le \min(4, M)$
• 마을에서 주어지는 기지국의 개수는 1ドル$개이다.
• 마을에서 주어지는 노드의 개수는 $M$개이다.

힌트