In the game of Royal Gems, you are given an <!-- MATH
$n \times m$
-->
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 a program that finds the maximum number of ruby gemstones that could be put on the board satisfying the above rules.