통신 시스템의 성능 저하

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

마을은 $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$개다.