도미노

파샤는 $n \times m$ 크기의 보드를 가지고 있다. 일부 칸은 검은색이고, 일부 칸은 초록색이며, 나머지 칸은 흰색이다. 파샤는 점이 28개인 일반 도미노 세트를 가지고 있다. 그는 다음 조건에 따라 이 도미노 중 일부를 보드에 놓으려 한다.

• 각 도미노는 인접한 두 칸을 정확히 차지한다.
• 검은색이 아닌 모든 칸은 정확히 하나의 도미노로 덮인다.
• 검은색 칸은 도미노로 덮이지 않는다.
• 초록색 칸에 있는 점의 총합 $g$를 최대로 만든다.

주어진 보드에서 $g$가 가질 수 있는 최댓값을 구하라.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 양의 정수 $n$과 $m$ ($1 \leq n \cdot m \leq 56$)으로 시작한다. 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 있다. $i$번째 줄은 보드의 $i$번째 행을 나타내며, W는 흰색 칸, B는 검은색 칸, G는 초록색 칸이다. 각 보드에는 초록색 칸이 하나 이상 있다. 마지막 테스트 케이스 다음 줄에는 0 두 개가 적혀 있으며, 이 줄은 처리하지 않는다. 테스트 케이스는 최대 500개이다.

각 테스트 케이스마다 Case x: g 형식으로 번호와 $g$의 최댓값을 출력한다. 조건을 만족하는 배치가 없으면 No solution을 출력한다.

다음 그림은 첫 번째 테스트 케이스에서 도미노를 놓는 방법을 보여준다.