Royal Gems

Time limit1sMemory limit128 MB

Summary

Fill each cell of an n by m board with one of four gems to maximize the ruby count while every ruby, emerald, and sapphire neighbors the required higher gems.

Level: Medium7 of 10
Topics: Dynamic programming, Backtracking, Bit manipulation, Matrix
Solved: No attempts yet

Problem

In the game of Royal Gems you get an $n \times m$ board and an unlimited supply of rubies, emeralds, sapphires, and diamonds. You place exactly one gemstone in every cell of the board, and the placement has to obey all three rules below.

Every ruby has an emerald, a sapphire, and a diamond among its neighbors.
Every emerald has a sapphire and a diamond among its neighbors.
Every sapphire has a diamond among its neighbors.

The neighbors of a cell are the cells directly above it, below it, to its left, and to its right, so a cell on the border of the board has fewer than four neighbors. A diamond carries no condition of its own.

Write a program that finds the largest number of rubies you can place on the board while all three rules hold.

Input

The input contains several test cases. Each test case is one line holding the number of rows $n$ and the number of columns $m$ , separated by a space. ( $1 < n < 8$ , $1 < m < 8$ )

The last line of the input is 0 0. That line is not a test case.

Output

For each test case print, on its own line, the largest number of rubies that can be placed on the board.

Examples1

Example 1
Input
```
2 2
2 3
3 3
0 0
```
Expected output
```
0
1
2
```