MDT 활용

Nlogonia 왕국은 매우 번영하고 있다. 왕 Constantourist는 주변 마을을 정복해 영토를 넓혔다. 그러나 이제 Constantourist의 삶이 끝나가면서, 그의 두 아들 Javasar와 Golangsar가 왕국의 운명을 결정해야 한다.

불필요한 전쟁으로 다음 왕을 정하는 대신, 두 아들은 왕국의 영토를 둘로 나누는 협상을 진행한다. Nlogonia는 남북 방향으로 N킬로미터, 동서 방향으로 M킬로미터인 직사각형 땅이다. 그래서 협상 초기 단계에서 두 아들은 왕국 경계에 평행한 분할선을 사용해 땅을 한 변의 길이가 1킬로미터인 N × M개의 정사각형 구획으로 나눌 수 있었다. 다음 단계는 이 구획을 두 아들에게 분배하는 것이다.

협상을 계속하기 전에 Javasar는 자신이 차지할 구획을 정해야 한다. 그는 이미 각 구획을 토양의 질에 따라 좋음 또는 나쁨으로 분류해 두었다. Javasar는 자신의 영역이 Nlogonia에서 최고로 인정받기를 바라므로, 좋은 토양의 구획만 선택할 계획이다. 게다가 완벽주의자인 그는 자신이 차지할 구획들이 정사각형을 이루어야 한다고 결정했다.

Javasar는 이런 조건 때문에 구획을 얼마 얻지 못할까 봐 걱정한다. 다행히도 Byteland로 떠난 모험 중에, 그는 고대의 마법 도구 MDT(Magical Divine Tool)를 발견했다. MDT는 활성화되면 Javasar가 현재 서 있는 구획의 토양의 질을 반전시킬 수 있다. 다시 말해, 활성화된 MDT는 나쁜 구획을 좋은 구획으로, 좋은 구획을 나쁜 구획으로 바꾼다.

이 편리한 도구와 함께 Javasar는 완벽한 계획을 세웠다! 그는 왕국 밖으로 나가 북서쪽 모서리에 있는 구획의 서쪽에 도착한 뒤, 아래 그림에 나오는 경로를 따라 각 구획을 정확히 한 번씩 방문한다. Javasar는 Nlogonia에 여러 번 들어가고 나온다. 이렇게 하면 왕국 안에서 MDT를 활성화하거나 비활성화하는 모습을 들키지 않으므로, 아무도 그가 도구를 조작하는 것을 보지 못한다. MDT는 마법적이고 신성하지만, 스스로 활성화되거나 비활성화되지는 않는다.

Javasar의 수석 고문으로서, 그가 MDT를 최적으로 활용할 때 조건을 만족하면서 얻을 수 있는 구획의 최대 개수를 알려주어야 한다.

첫 번째 줄에는 두 정수 N과 M(1 ≤ N, M ≤ 1000)이 주어지며, 이는 각각 Nlogonia의 남북 방향과 동서 방향 길이(킬로미터)를 나타낸다. 다음 N개의 줄 각각에는 M개의 문자로 이루어진 문자열이 주어지며, 각 문자는 대문자 “G” 또는 대문자 “B”로 해당 구획의 토양의 질이 각각 좋음 또는 나쁨임을 나타낸다. 왕국의 구획에 대한 설명은 북쪽에서 남쪽으로, 서쪽에서 동쪽으로 주어진다.

Javasar가 MDT를 최적으로 활용할 때 조건을 만족하면서 얻을 수 있는 구획의 최대 개수를 나타내는 정수를 한 줄에 출력한다.