Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Royal Gems
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 274 Accepted: 33

Description

In the game of Royal Gems, you are given an n × m board and arbitrarily large number of ruby, emerald, sapphire, and diamond gemstones. You must put one gemstone in each cell of the board according to the following rules:

1) Every ruby has an emerald, a sapphire and a diamond in his neighbors.
2) Every emerald has a sapphire and a diamond in her neighbors.
3) Every sapphire has a diamond in his neighbors.

A neighbor of a cell is one of the four cells that are directly above, below, left, or right of the cells. Write aprogram that finds the maximum number of ruby gemstones that could be put on the board satisfying the above rules.

Input

There are multiple test cases in the input. Each test case consists of n (1 < n < 8) and m (1 < m < 8). The input terminates with a line containing 0 0.

Output

For each test case, write a single line containing the maximum number of ruby gemstones on the board.

Sample Input

```2 2
2 3
3 3
0 0```

Sample Output

```0
1
2```

Source

[Submit]   [Go Back]   [Status]   [Discuss]