로열 젬

로열 젬 게임에서는 $n \times m$ 크기의 판과 루비, 에메랄드, 사파이어, 다이아몬드 네 종류의 보석이 주어진다. 보석은 종류마다 얼마든지 쓸 수 있고, 판의 모든 칸에 보석을 하나씩 놓아야 한다. 놓는 방법은 다음 세 규칙을 모두 지켜야 한다.

1. 모든 루비는 이웃에 에메랄드, 사파이어, 다이아몬드가 각각 하나 이상 있다.
2. 모든 에메랄드는 이웃에 사파이어와 다이아몬드가 각각 하나 이상 있다.
3. 모든 사파이어는 이웃에 다이아몬드가 하나 이상 있다.

어떤 칸의 이웃은 그 칸의 바로 위, 아래, 왼쪽, 오른쪽에 붙어 있는 칸이다. 그래서 판 가장자리에 있는 칸은 이웃이 넷보다 적다. 다이아몬드에 붙는 조건은 없다.

세 규칙을 모두 지키면서 판에 놓을 수 있는 루비의 최대 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄이고, 판의 세로 길이 $n$과 가로 길이 $m$이 공백을 사이에 두고 주어진다. ($1 < n < 8$, $1 < m < 8$)

입력의 마지막 줄은 0 0이다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 판에 놓을 수 있는 루비의 최대 개수를 한 줄에 하나씩 출력한다.