Miner#4875
Every miner knows that the likelihood of stepping on a mine greatly depends on how skillfully they are placed.
The popular game "Minesweeper" is played on a rectangular grid consisting of w \times h cells. Each cell either contains a mine or displays a number representing the count of mines in the eight surrounding cells (a number from to ).
Your task is to determine the minimum number of mines needed so that no cell is without a mine in it or in its neighboring cells.
The first line of the input contains two integers and (1 \le w, h \le 1000), separated by a space, representing the width and height of the field, respectively.
Output a single line with the minimum number of mines required so that each cell on the game field either contains a mine or has a number greater than zero.
The second example (a 5 \times 5 field) is illustrated in the following image:
Example 1